題目描述：
實(shí)現(xiàn)int sqrt(int x)函數(shù)。
計(jì)算并返回x的平方根，其中x?是非負(fù)整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
示例 1:
輸入:4輸出:2
示例 2:
輸入:8輸出:2說明:8 的平方根是 2.82842..., ?? ? 由于返回類型是整數(shù)，小數(shù)部分將被舍去。
一想到平方根，我第一時(shí)間想到用2分法的方法去計(jì)算，用一個(gè)while循環(huán)來控制終止條件。但是突然想到在數(shù)值分析中學(xué)到的牛頓迭代法，它的收斂速度比二分法要快，于是用牛頓迭代法寫了下面一段代碼。
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;
? ? }
};
但是在提交時(shí)有個(gè)測試案例卻通不過，那就是輸入為2147395599時(shí)輸出結(jié)果為46340，但是正確結(jié)果應(yīng)該為46339，因?yàn)?147395599的平方根為46,339.999989，筆者想了很久，先是檢查了一遍代碼，這是牛頓迭代法的公式?jīng)]錯(cuò)，難道牛頓迭代法在計(jì)算這個(gè)測試用例的時(shí)候出了問題？于是我開始斷點(diǎn)跑測試，發(fā)現(xiàn)在倒數(shù)第二次sqrt就等于46340.0，為什么會(huì)這樣呢，然后我往前幾次看，發(fā)現(xiàn)了問題，因?yàn)檫@里我的sqrt, temp是float，精度不夠，在迭代進(jìn)行帶一定步驟的時(shí)候就自動(dòng)舍棄了后面的數(shù)字，導(dǎo)致bug的發(fā)生。
最后筆者把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;
? ? }
};
代碼完美運(yùn)行
