我用C++编写代码,这需要一个中间步骤来检查一个数是否是正方形。我写了下面的代码。
int sqrt_of_t = (int)sqrt(t);
if (sqrt_of_t*sqrt_of_t != t)
{
cout << "NO" << endl;
}
这段代码在我的系统中给出了正确的结果,但是当它通过Codeforce中的在线判断时失败了。它失败的情况并没有任何溢出或任何相关的东西(非常小的测试用例)。那么,有没有人能解释一下哪里出了问题,并提出一些替代方法来检查一个数字是否是完美的正方形,它可以在所有系统上工作,不会显示这样的行为,这里t
也是一个int。
3条答案
按热度按时间g52tjvyc1#
sqrt()
返回一个浮点数,您可以将其转换为int,它会截断任何小数部分。问题是浮点数不能精确地表示所有整数,因此您可能会得到类似19.9999999999999的结果,您期望它是20,但当转换为整数时实际上是19。要修复此问题,请改用舍入:
watbbzwu2#
sqrt
,在许多系统上返回近似值。例如,
sqrt(25)
可能返回类似于4.99999999的值。因此,4.99999999 * 4.99999999略小于25。
我的建议是在数字空间中做一个二进制搜索,看看这个数字是否是一个完美的平方。当你需要精确的结果时,避免使用浮点。
webghufk3#
这是Knuth非常有趣的算法,只需要移位和加法就可以计算整数平方根。它对非平方输入进行四舍五入。
这个方法是将每一位设置为1,从高到低,保持到目前为止计算出的预期根的平方。如果每一位产生的平方不大于输入值,那么它就被“或“到结果中。它可以被修改以检测预期是精确平方的情况。
我是为了大家的兴趣而添加的。二进制搜索的建议很好。也许更好,除非你在一台没有快速乘法的机器上工作。