美文网首页
31. Sqrt(x) FROM Leetcode

31. Sqrt(x) FROM Leetcode

作者: 时光杂货店 | 来源:发表于2017-03-17 16:55 被阅读11次

    题目

    Implement int sqrt(int x).

    Compute and return the square root of x.

    频度: 4

    解题之法

    class Solution {
    public:
        int mySqrt(int x) {
            
            
          long r = x;
          while (r*r > x)
            r = (r + x/r) / 2;
            
          return r;
            
        }
    };
    

    分析

    这种解法主要利用了牛顿迭代法。

    226.jpg

    这种算法的原理很简单,我们仅仅是不断用(x,f(x))的切线来逼近方程x2-a=0的根。根号a实际上就是x2-a=0的一个正实根,这个函数的导数是2x。

    具体推导如下:

    227.jpg

    代入f(x)=x2-a得到x-(x2-a)/(2x),也就是(x+a/x)/2。

    相关文章

      网友评论

          本文标题:31. Sqrt(x) FROM Leetcode

          本文链接:https://www.haomeiwen.com/subject/rzienttx.html