我认为下面的代码存在精度问题:
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时要小心。这些类型的错误的可能性随着整数范围的增加而增加。
9条答案
按热度按时间vaqhlq811#
您可以使用浮点平方根的结果作为提示。将其转换为整数。检查平方是否相等。如果它更高或更低,则递减或递增它,然后重新检查平方,并继续,直到您将参数绑定为:c1c1〈= n〈=(c1+1)(c1+1)
ubbxdtey2#
你可以使用std::sqrt作为猜测和乘法测试:
f5emj3cl3#
您使用
round
。round
将数字四舍五入到最近的四舍五入。只有当n是完全平方时,该函数才为真。efzxgjgh4#
mmmm不要使用float/double作为true/false的结果(你最终会遇到近似问题)更好的是整数方法:
div()是不带余数的整数除法(您可以在某些方面使用GCD())
我知道,我知道……一定要注意溢出的问题
bmp9r5qi5#
Sqrt(4)可以返回1.9999
不,4和2完全可以表示为二进制浮点数。没有精度问题。
问题是
long long
有64位的精度,但double
只有52位,所以所有依赖于调用sqrt(double)
的解决方案都会在达到这个限制时开始失败。下面是一个简单的测试程序:这是我电脑上的输出:
注意
log(4503599627370497)/log(2) = 52
。如果你不关心那么大的数字,你可以使用简单的解决方案,只检查sqrt
是否返回整数结果。i86rm4rw6#
您可以简单地检查
sqrt()
的下限和上限:5hcedyr07#
你可以使用一个范围作为你的返回布尔值,尽管它可能会导致不精确的输出,这取决于你的要求有多严格:
6tdlim6h8#
密码没问题!
我花时间写了一个小测试。由于输入范围有限,我们可以简单地验证每个输入的函数。
请注意,我确实必须为
sqrt
函数添加一个显式强制转换,以便编译(使用MS VC++ 10)。结果?所有值都通过!问题一定出在使用函数的代码中。也许可以给函数添加输入范围验证。
dvtswwa39#
long long
是一个整数类型。因此,您的+0.5在截断时丢失。