c++ 检查一个数是否是完全平方数,

kxkpmulp  于 2023-04-08  发布在  其他
关注(0)|答案(9)|浏览(317)

我认为下面的代码存在精度问题:

bool isPerfectSquare(long long n){
    long long squareRootN=(long long)(sqrt(n)+0.5);

    return squareRootN*squareRootN == n;
}

如何解决?PS:1〈= n〈= 10^10
Sqrt(4)可以返回1.9999 =〉1,所以我添加了0.5,以便在四舍五入时变为2。sqrt返回浮点数。
这是我找到的一个解释,但仍然无法修复代码:
嗨,看起来你也是浮点值的受害者。如果可能的话,你应该总是避免浮点比较。随着数字范围的增加,情况变得更糟。比如说,当你给float赋值a=4.0时,它会被存储为4.000...01111或3.999999...9978或类似的值。所以当你在int类型中输入case a square root时要小心。这些类型的错误的可能性随着整数范围的增加而增加。

vaqhlq81

vaqhlq811#

您可以使用浮点平方根的结果作为提示。将其转换为整数。检查平方是否相等。如果它更高或更低,则递减或递增它,然后重新检查平方,并继续,直到您将参数绑定为:c1c1〈= n〈=(c1+1)(c1+1)

ubbxdtey

ubbxdtey2#

你可以使用std::sqrt作为猜测和乘法测试:

#include <cmath>
#include <limits>
#include <iostream>

bool isPerfectSquare(long long n){
    double guess = sqrt(n);
    long long r = std::floor(guess);
    if(r*r == n) return true;
    else {
        r = std::ceil(guess);
        return r*r == n;
    }
}

int main() {
    const long long Limit = std::pow(10, std::numeric_limits<long long>::digits10 / 2);
    std::cout << " Limit: " << Limit << '\n';
    for (long long i = 0; i < Limit; ++i) {
        if( ! isPerfectSquare(i*i)) {
            std::cout << "Failure: " << i << '\n';
            return 0;
        }
    }
    std::cout << "Success\n";
}
f5emj3cl

f5emj3cl3#

您使用round

bool isPerfectSquare(long long n) {
    long long squareRootN = (long long)round((sqrt(n)));
    
    if(squareRootN * squareRootN == n) {
        return true; 
    } else {
        return false; 
    }
}

round将数字四舍五入到最近的四舍五入。只有当n是完全平方时,该函数才为真。

efzxgjgh

efzxgjgh4#

mmmm不要使用float/double作为true/false的结果(你最终会遇到近似问题)更好的是整数方法:

boolean is_square(long long n)
   {
      long long a=n;
      while (a*a>n)
      {
         a=div(a+div(n,a),2);
      }
      return a*a==n;
   }

div()是不带余数的整数除法(您可以在某些方面使用GCD())
我知道,我知道……一定要注意溢出的问题

bmp9r5qi

bmp9r5qi5#

Sqrt(4)可以返回1.9999
不,4和2完全可以表示为二进制浮点数。没有精度问题。
问题是long long有64位的精度,但double只有52位,所以所有依赖于调用sqrt(double)的解决方案都会在达到这个限制时开始失败。下面是一个简单的测试程序:

#include <iostream>
#include <math.h>
#include <stdlib.h>

bool isPerfectSquare(long long n)
{
    double root = sqrt(n);
    return floor(root) == root;
}

void check(long long x)
{
    if (!isPerfectSquare(x))
        std::cerr << x << " should be perfect\n", exit(1);
    if (isPerfectSquare(x-1))
        std::cerr << x-1 << " should NOT be perfect\n", exit(1);
    if (isPerfectSquare(x+1))
        std::cerr << x+1 << " should NOT be perfect\n", exit(1);
}

int main()
{
    for (long long i = 2; i < 3037000499; ++i)
        check(i * i);
    std::cout << "all tests passed\n";
}

这是我电脑上的输出:

4503599627370497 should NOT be perfect

注意log(4503599627370497)/log(2) = 52。如果你不关心那么大的数字,你可以使用简单的解决方案,只检查sqrt是否返回整数结果。

i86rm4rw

i86rm4rw6#

您可以简单地检查sqrt()的下限和上限:

bool isSquare (long long number)
{
    double root = sqrt(number);
    double floor = std::floor(root);
    double ceil = std::ceil(root);

    return (floor * floor == number) && (ceil * ceil == number);
}
5hcedyr0

5hcedyr07#

你可以使用一个范围作为你的返回布尔值,尽管它可能会导致不精确的输出,这取决于你的要求有多严格:

double threshold = 0.01;

return (squareRootN*squareRootN > n-threshold) && (squareRootN*squareRootN < n+threshold);
6tdlim6h

6tdlim6h8#

密码没问题!
我花时间写了一个小测试。由于输入范围有限,我们可以简单地验证每个输入的函数。
请注意,我确实必须为sqrt函数添加一个显式强制转换,以便编译(使用MS VC++ 10)。

#include <math.h>
#include <iostream>
#include <set>

bool isPerfectSquare(long long n){
    long long squareRootN=(long long)(sqrt((double)n)+0.5);

    return squareRootN*squareRootN == n;
}

int main()
{
    // for the input range,
    // generate a set with numbers that are known to be perfect squares.
    // all the rest are not.
    std::set<long long> perfectSquares;
    for(long long i = 1ll; i <= 100000ll; ++i) {
        perfectSquares.insert(i*i);
    }
    std::cout << "Created lookup." << std::endl;

    // now test the function for all the numbers in the input range   
    int progress = -1;
    for(long long i = 1ll; i <= 10000000000ll; ++i) {
        bool expected = (perfectSquares.count(i) == 1);
        bool actual = isPerfectSquare(i);

        if(expected != actual) {
            std::cout << "Failed for " << i << std::endl;
        }

        int newprogress = i / 100000000ll;
        if(newprogress != progress) {
            progress = newprogress;
            std::cout << "Progress " << progress << "%" << std::endl;
        }
    }
    std::cout << "Test finished." << std::endl;
}

结果?所有值都通过!问题一定出在使用函数的代码中。也许可以给函数添加输入范围验证。

dvtswwa3

dvtswwa39#

long long是一个整数类型。因此,您的+0.5在截断时丢失。

相关问题