LeetCode69. Sqrt(x) -- 求一個(gè)數(shù)的開方

ddongjian0000 發(fā)布于2019-07-30 16:55 / 1554人閱讀

摘要：牛頓迭代法的原理很簡單，其實(shí)是根據(jù)在附近的值和斜率，估計(jì)和軸的交點(diǎn)，因此牛頓迭代法的公式為其實(shí)就是求切線與軸的交點(diǎn)。代碼利用牛頓法進(jìn)行的更新，比直接從開始遍歷所作的循環(huán)要少牛頓迭代法的基本原理，請(qǐng)參考牛頓迭代法求開平方

描述

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example：

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

分析

該題就是求一個(gè)數(shù)的開平方，此處忽略這種直接用int(x ** 0.5)的做法；

最簡單的求解方式是從1進(jìn)行遍歷，直到找到一個(gè)數(shù)n，滿足$n^2>x$，則此時(shí)$n-1$就是要找的值，但是該方法需要遍歷$int(sqrt x)$次，當(dāng)$x$的數(shù)值很大時(shí)，需要遍歷的次數(shù)太多；

所以這里采用牛頓迭代法來進(jìn)行開方，牛頓迭代法能開任意數(shù)的平方，并能找到一個(gè)逼近解，當(dāng)然該題只需要找到對(duì)應(yīng)的整數(shù)解就可以。牛頓迭代法的原理很簡單，其實(shí)是根據(jù)$f(x)=x^2 - a$在$x_0$附近的值和斜率，估計(jì)$f(x)$和$x$軸的交點(diǎn)，因此牛頓迭代法的公式為：

$$x_{n+1}=x_n - frac{f(x_n)}{f^{"}(x_n)}$$

其實(shí)就是求切線與x軸的交點(diǎn)。

代碼

class Solution:
    def mySqrt(self, x):
        """
        利用牛頓法進(jìn)行x0的更新，比直接從1開始遍歷所作的循環(huán)要少
        :type x: int
        :rtype: int
        """
        x0 = 1
        while True:
            x1 = x0 - (x0 ** 2 - x)/(2*x0)
            if int(x1) == int(x0):
                break
            else:
                x0 = x1
        return int(x0)

牛頓迭代法的基本原理，請(qǐng)參考：
牛頓迭代法求開平方