優化的方式，如果一個號碼是一個完美的方形

我在我分配的問題找到一個數是否是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"; 
}

它工作正常。

是否可以稱爲更優化的解決方案比別人？

來源

2014-08-27 Sachin Gadagi

雖然一個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; 
}

來源

2014-08-27 16:29:02

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

另一種說法做什麼限制，一個（非負）號碼是一個平方數，是它的平方根是再次整數 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))

來源

2014-08-27 16:30:06 PauloASilva

只有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; 
}

來源

2014-08-27 16:31:27 user3250183

你需要知道的的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的鏈接以獲得更好的方法。

來源

2014-08-27 16:44:56 Nicolas

我給你推薦這一個

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他可以做的更好還是

我希望它能幫助.....

有一個愉快的一天....

來源

2014-08-27 17:09:40

您的解決方案是更優化，但它可能無法正常工作。由於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)); 

}

來源

2014-08-27 17:59:50 ragnarius

這是一個尋找完美的方塊R不簡單Python代碼：

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

來源

2018-01-19 02:44:08

優化的方式，如果一個號碼是一個完美的方形

回答

相關問題