首页 > 代码库 > LeetCode: Sqrt(x) [069]

LeetCode: Sqrt(x) [069]

2024-07-06 14:25:44   216人阅读

【题目】


Implement int sqrt(int x).

Compute and return the square root of x.



【题意】

实现 int sqrt(int x)，计算并返回平方根。


【思路】

       

        用牛队迭代法求解，本题可以转化为求 f(n)=n^2-x=0的解


        用牛顿迭代法不断逼近真实解，假设曲线上有点(n[i],f(n[i]))


        则这点出的斜率为2n[i], 通过该点的直线方程为 y=2n[i](n-n[i])+f(n[i]);


        该直线与横轴的焦点通过求解y=2n[i](n-n[i])+f(n[i])得到，也即为从n[i]到n[i]+1的迭代公式为

                                                        

                                                        n[i+1]=(n[i]+x/n[i])/2;


        经过若干次迭代后，n[i]会迅速收敛。


        当相邻两个解的差小于某个阈值时我们认为就得到了本题的解。


【代码】

class Solution {
public:
    int sqrt(int x) {
        if(x<=0)return 0;   
        
        double result=100;
        double newResult=(result + x/result)/2;
        while(abs(result-newResult)>0.00001){
            result = newResult;
            newResult = (result + x/result)/2;
        }
        return (int)result;
    }
};


联系
我们