学步园

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;
    }
};