今天的這篇文章是我在刷算法題的時(shí)候遇到的，最簡單的方法是直接調(diào)用java里面的Sqrt函數(shù)，不過有時(shí)候題目中會(huì)要求我們不能使用庫函數(shù)，所以在這里我們自己定義Sqrt方法。

最常見的思路有兩種，第一種是二分法，第二種是牛頓的微積分思想。沒錯(cuò)，想當(dāng)年大學(xué)時(shí)候?qū)W了很久很痛苦的微積分，被我第一次派上用場(chǎng)了。對(duì)于這兩種方法我們一個(gè)一個(gè)看。

一、二分法

二分法的思想很簡單，就是從0到N不斷的去縮小范圍來找一個(gè)一個(gè)滿足精度的最佳值。我們舉一個(gè)函數(shù)的例子：

1.jpg

這就是二分法的思想，求平方根也是，我們從0到value取出中間值，然后不斷地比較，假設(shè)value=10，查找區(qū)間為（0，10），這時(shí)候?。?,10）的中間值mid=5，mid*mid再和value比較之后，確定下一次查找的區(qū)間變?yōu)椋?，5），依次類推。一直到滿足我們需要的精度即可。下面我們使用java代碼實(shí)現(xiàn)一下：

    static double MySqrt(int value, double t){
        if (value < 0 || t<0)
            return 0;
        double left = 0;
        double right = value;
        double mid = (right + left) / 2;
        double offset = 2*t ;
        while (offset>t){
            double temp = mid*mid;
            if (temp > value){
                right = (left + right) / 2;
                offset = temp - value;
            }
            if (temp <= value){
                left = (left + right) / 2;
                offset = value - temp;
            }
            mid = (left + right) / 2;
        }
        return mid;
    }

在這里value就是我們要求的數(shù)字，t表示的是精度。這個(gè)方法在這，大家可以測(cè)試一遍。不過在這里有一個(gè)小小的問題需要我們?nèi)プ⒁猓?/p>

如果我們對(duì)整數(shù)9取平方根，結(jié)果不是3，這里有精度損失，損失的原因之一是和計(jì)算機(jī)有關(guān)的，因?yàn)橛?jì)算機(jī)的底層其實(shí)只有0和1，所以會(huì)無限的接近，而不能精確表示。

以上就是二分法求解的思想，這個(gè)思想很簡單，不過實(shí)現(xiàn)的方法卻是有一點(diǎn)點(diǎn)麻煩。在這里我們開始介紹第二種方法，那就是牛頓的微積分思想
二、牛頓迭代法

牛頓的微積分的思想就是無限接近，在這里提一句，如果你是數(shù)學(xué)大佬就不要追究思想到底是啥了。對(duì)于求平方根來說，使用切線來無限逼近的方式有時(shí)候能起到意想不到的效果。

設(shè)r是f(x) = 0的根，選取x0作為r初始近似值，過點(diǎn)（x0,f(x0)）做曲線y = f(x)的切線L，

L的方程為y = f(x0)+f'(x0)(x-x0)，求出L與x軸交點(diǎn)的橫坐標(biāo) x1 = x0-f(x0)/f'(x0)，稱x1為r的一次近似值。

過點(diǎn)（x1,f(x1)）做曲線y = f(x)的切線，并求該切線與x軸交點(diǎn)的橫坐標(biāo) x2 = x1-f(x1)/f'(x1)，稱x2為r的二次近似值。

重復(fù)以上過程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，稱為r的n+1次近似值，上式稱為牛頓迭代公式。

我們使用一張圖來演示一下：

2牛頓.png

這種方式也很好理解。所以我們直接來看實(shí)現(xiàn)：

static double SqrtIterator(int value,double t){
    double temp = value;
    while (fabs(temp*temp-value)>t){
        temp=(temp+value/temp) / 2.0;
    }
    return temp;
}
//取絕對(duì)值
private static double fabs(double a) {
    return (a < 0) ? -a : a;
}

上面的方法同樣可以表示。而且我們可以看到，牛頓的這個(gè)方法其實(shí)更加的簡單。而且精度也更好。