LeetCode——Sqrt(x)

Description:

Implement int sqrt(int x).

Compute and return the square root of x.

 好好学习数学还是非常有用的，牛顿迭代法 求解。

    计算x² = n的解，令f(x)=x²-n，相当于求解f(x)=0的解，如左图所示。

   首先取x₀，如果x₀不是解，做一个经过(x₀,f(x₀))这个点的切线，与x轴的交点为x₁。

   同样的道理，如果x₁不是解，做一个经过(x₁,f(x₁))这个点的切线，与x轴的交点为x₂。

   以此类推。

   以这样的方式得到的x_i会无限趋近于f(x)=0的解。

   判断x_i是否是f(x)=0的解有两种方法：

   一是直接计算f(x_i)的值判断是否为0，二是判断前后两个解x_i和x_i-1是否无限接近。

 

public class Solution {
    public int mySqrt(int x) {
        if (x ==0)  
           return 0;  
        double pre;  
        double cur = 1;  
        do  
        {  
            pre = cur;  
            cur = x / (2 * pre) + pre / 2.0;  
        } while (Math.abs(cur - pre) > 0.00001);  
        return (int) cur;  

        
    }
}