优化的方式，如果一个号码是一个完美的方形

问题描述：

我在我分配的问题找到一个数是否是perfect square与否：优化的方式，如果一个号码是一个完美的方形

完美广场是代数结构的元素等于另一个元素的正方形。

例如：4，9，16等

什么我的朋友们所做的是，如果n是多少，他们循环n - 1倍计算n * n：

// just a general gist 
int is_square = 0; 
for (int i = 2; i < n; i++) 
{ 
    if ((i * i) == n) 
    { 
    std::cout << "Yes , it is"; 
    is_square = 1; 
    break; 
    } 
} 
if (is_square == 0) 
{ 
    std::cout << "No, it is not"; 
}

我想出了一个解决方案如下图所示：

if (ceil(sqrt(n)) == floor(sqrt(n))) 
{ 
    std::cout << "Yes , it is"; 
} 
else 
{ 
    std::cout << "no , it is not"; 
}

它工作正常。

是否可以称为更优化的解决方案比别人？

虽然一个Java问题，这些算法也应该适用于C++（以及接受的答案使用C++）：[确定整数的平方根是否为整数的最快方法]（http://stackoverflow.com/questions/295579/fastest-way- to-determine-if-an-integer-square-root-is-an-integer） – interjay 2014-08-27 16:31:26

除了所有其他的答案之外，还有一个bu您可以立即使用的一些技巧消除案例。例如，所有正方形以1,4,5,6,9和00结尾。 – Ben 2014-08-27 16:33:26

我不认为你的解决方案是100％的傻瓜证明。这可能是sqrt（k * k）返回一个小于k（k-epsilon）的数字，然后floor将与ceil不同。 – ragnarius 2014-08-27 18:29:12

答

尝试和真正的遗体：

double sqrt(double x); // from lib 

bool is_sqr(long n) { 
    long root = sqrt(n); 
    return root * root == n; 
}

答

我不知道你有，但完全平方数的定义是清晰

另一种说法做什么限制，一个（非负）号码是一个平方数，是它的平方根是再次整数 in wikipedia

IF SQRT(n) == FLOOR(SQRT(n)) THEN 
    WRITE "Yes it is" 
ELSE 
    WRITE "No it isn't"

个

例子sqrt(9) == floor(sqrt(9))，sqrt(10) == floor(sqrt(10))

只有n为1或0时，SQRT（n）== FLOOR（N）才是真吗？ – horriblyUnpythonic 2014-08-27 17:15:40

你说得对，它必须是sqrt（n）== floor（sqrt（n）） – PauloASilva 2014-08-27 17:22:49

答

#include <iostream> 
using namespace std; 
void isPerfect(int n){ 
    int ctr=0,i=1; 
    while(n>0){ 
     n-=i; 
     i+=2; 
     ctr++; 
    } 
    if(!n)cout<<"\nSquare root = "<<ctr; 
    else cout<<"\nNot a perfect square"; 
} 
int main() { 
    isPerfect(3); 
    isPerfect(2025); 
    return 0; 
}

答

你需要知道的的sqrt（x）函数的复杂性在您的计算机上，以避免与其他方法进行了比较。顺便说一句，你正在调用sqrt（n）两次;考虑将它存储到一个变量中（即使编译器可能为你做了这个）。

如果使用类似牛顿法的方法，则sqrt（x）的复杂度在O(M(d))中，其中M（d）用于测量乘以两个d数字所需的时间。 Wikipedia

你的朋友的方法是（n-2）乘法运算（最坏的情况），因此它的复杂度就像O(n * M(x))，其中x是一个越来越大的数字。

您的版本只使用sqrt（）（ceil和floor可以忽略，因为它们不断复杂），这使得它成为O(M(n))。

O(M(n)) < O(n * M(x)) - 您的版本比您的朋友更优化，但效率并非最高。看看interjay的链接以获得更好的方法。

答

我给你推荐这一个

if(((unsigned long long)sqrt(Number))%1==0) // sqrt() from math library 
{ 
    //Code goes Here 
}

它的工作原理，因为....所有整数（&仅正整数）是1

，因此该解决方案正倍数.....

您还可以运行基准测试，如：我没有在MSVC 2012

#include <iostream> 
#include <conio.h> 
#include <time.h> 
#include <math.h> 

using namespace std; 

void IsPerfect(unsigned long long Number); 

void main() 
{ 
    clock_t Initial,Final; 
    unsigned long long Counter=0; 
    unsigned long long Start=Counter; 
    Start--; 
    cout<<Start<<endl; 
    Initial=clock(); 
    for(Counter=0 ; Counter<=100000000 ; Counter++) 
    { 
     IsPerfect(Counter); 
    } 
    Final=clock(); 
    float Time((float)Final-(float)Initial); 
    cout<<"Calculations Done in "<< Time ; 
    getch(); 
} 

void IsPerfect(unsigned long long Number) 
{ 
    if(ceil(sqrt(Number)) == floor(sqrt(Number))) 
    //if(((unsigned long long)sqrt(Number))%1==0) // sqrt() from math library 
    { 
    } 

}

下面的代码你的代码了13590个时间单位

矿只是10049个时间单位

而且我使用一些额外的步骤，是类型转换

我

(unsigned long long)sqrt(Number))

没有t他可以做的更好还是

我希望它能帮助.....

有一个愉快的一天....

答

您的解决方案是更优化，但它可能无法正常工作。由于sqrt(x)可能返回真正的平方根+/-小量，3个不同根必须进行测试：

bool isPerfect(long x){ 
    double k = round(sqrt(x)); 

    return (n==(k-1)*(k-1)) || (n==k*k) || (n==(k+1)*(k+1)); 

}

答

这是一个寻找完美的方块R不简单Python代码：

import math 
n=(int)(input()) 
giv=(str)(math.sqrt(n)) 
if(len(giv.split('.')[1])==1): 
    print ("yes") 
else: 
    print ("No")

优化的方式，如果一个号码是一个完美的方形

相关推荐