學步園

Implement int sqrt(int x).

Compute and return the square root of x.

思路：求平方根比較簡單的方法是牛頓法。選取一個自然數k,判斷|k^2-x|是否小於1，小於則是k,不小於則重新給k賦值。

假設k>sqrt(x)，則x/k<sqrt(x)，取k為一個大於最終值，一個小於最終值的中間值，無限逼近最終結果。

即k=(k+x/k)/2

class Solution {
public:
    double abs(double a)
    {
        return a>=0 ? a :  -1*a;
    }
    int sqrt(int x) {
        double a = (double)x;
        while(abs(a*a-x)>=1)
        { 
           a = (a + x*1.0/a)*1.0/2;
        }
        return (int)a;
    }
};