题目
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。
网友评论