LeetCode-69.Sqrt(x)-牛頓疊代法

題目：

實作 int sqrt(int x) 函數。
計算并傳回 x 的平方根，其中 x 是非負整數。
由于傳回類型是整數，結果隻保留整數的部分，小數部分将被舍去。

示例 1:

輸入: 4
輸出: 2
示例 2:

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,  由于傳回類型是整數，小數部分将被舍去。
           

解題思路：

注：使用 while(r * r> x)會溢出

牛頓疊代法：計算x2 = n的解，令f(x)=x2-n，相當于求解f(x)=0的解。 首先取x0，如果x0不是解，做一個經過(x0,f(x0))這個點的切線，與x軸的交點為x1。 同樣的道理，如果x1不是解，做一個經過(x1,f(x1))這個點的切線，與x軸的交點為x2。 以此類推。 以這樣的方式得到的xi會無限趨近于f(x)=0的解。 判斷xi是否是f(x)=0的解有兩種方法： 一是直接計算f(xi)的值判斷是否為0，二是判斷前後兩個解xi和xi-1是否無限接近。

另一種解釋：設r是f(x) = 0的根，選取x0作為r初始近似值，過點（x0,f(x0)）做曲線y = f(x)的切線L，L的方程為

y = f(x0)+f'(x0)(x-x0)

，求出L與x軸交點的橫坐标 x1 = x0-f(x0)/f’(x0)，稱x1為r的一次近似值。 過點（x1,f(x1)）做曲線y = f(x)的切線，并求該切線與x軸交點的橫坐标

x2 = x1-f(x1)/f'(x1)

，稱x2為r的二次近似值。重複以上過程，得r的近似值序列，其中

x(n+1)=x(n)－f(x(n))/f'(x(n))

，稱為r的n+1次近似值，上式稱為牛頓疊代公式。

經過(xi, f(xi))這個點的切線方程為

f(x) = f(xi) + f '(xi)(x - xi)

，其中f’(x)為f(x)的導數，本題中為2x。令切線方程等于0，即可求出

xi+1=xi - f(xi) / f'(xi)

。 繼續化簡：

xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2

。

public static int mySqrt(int x) {
        int r;
        if(x <= 1)
            return x;
        r = x;
        while(r > x / r)
            r = (r + x / r)/2;
        return(r);
    }
           

切線方程： 曲線C：y=f(x),曲線上點P(a,f(a)) f(x)的導函數f '(x)存在，以P為切點的切線方程：

y-f(a)=f '(a)(x-a)