题目描述：
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入:4输出:2
示例 2:
输入:8输出:2说明:8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
一想到平方根，我第一时间想到用2分法的方法去计算，用一个while循环来控制终止条件。但是突然想到在数值分析中学到的牛顿迭代法，它的收敛速度比二分法要快，于是用牛顿迭代法写了下面一段代码。
class Solution {
public:
int mySqrt(int x) {
if (x<0) return 0;
int ans;
float sqrt, temp;
sqrt = 1;
temp = 0;
while (sqrt - temp > 0.001|| sqrt - temp <- 0.001)
{
temp = sqrt;
sqrt = 0.5*(x/sqrt + sqrt);
}
ans = (int)sqrt;
return ans;
}
};
但是在提交时有个测试案例却通不过，那就是输入为2147395599时输出结果为46340，但是正确结果应该为46339，因为2147395599的平方根为46,339.999989，笔者想了很久，先是检查了一遍代码，这是牛顿迭代法的公式没错，难道牛顿迭代法在计算这个测试用例的时候出了问题？于是我开始断点跑测试，发现在倒数第二次sqrt就等于46340.0，为什么会这样呢，然后我往前几次看，发现了问题，因为这里我的sqrt, temp是float，精度不够，在迭代进行带一定步骤的时候就自动舍弃了后面的数字，导致bug的发生。
最后笔者把float改为double，代码如下
class Solution {
public:
int mySqrt(int x) {
if (x<=0) return 0;
int ans;
double sqrt, temp;
sqrt = 1;
temp = 0;
while (sqrt - temp > 0.001|| sqrt - temp <- 0.001)
{
temp = sqrt;
sqrt = 0.5*(x/sqrt + sqrt);
}
ans = (int)sqrt;
return ans;
}
};
代码完美运行
网友评论