LeetCode69. Sqrt(x) -- 求一個數的開方

ddongjian0000 發布于2019-07-30 16:55 / 1562人閱讀

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

描述

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.

分析

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

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

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

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

其實就是求切線與x軸的交點。

代碼

class Solution:
    def mySqrt(self, x):
        """
        利用牛頓法進行x0的更新，比直接從1開始遍歷所作的循環要少
        :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)

牛頓迭代法的基本原理，請參考：
牛頓迭代法求開平方

GPU云服務器云服務器 linux求一列數據的和 Sqrt LeetCode x69x64 php

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/41904.html

[Leetcode] Sqrt 開方

摘要：二分搜索復雜度時間因為整數長度有限空間思路我們知道必定存在這么兩個整數和，所以我們要做的其實就是縮小這個的范圍。代碼牛頓迭代法復雜度時間空間思路更好的解法是用數學方法，牛頓法是非常經典的求解方程的方法。 Sqrt Implement int sqrt(int x). Compute and return the square root of x. 二分搜索復雜度時間 O(1) ...

BlackFlagBin 2019-08-14 12:25 評論0 收藏0
leetcode-69. Sqrt(x)

摘要：題目思路牛頓迭代法，導數方程，任何函數，求解某個均可以轉化為此后就可以用牛頓迭代法，不斷逼近實際待求值。牛頓迭代共識應用迭代思想，類似于動態規劃思想，，進行動態推斷處理題目： Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-neg...

Yuqi 2019-07-30 17:22 評論0 收藏0
[LeetCode] 69. Sqrt(x)

Problem 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 an...

SQC 2019-08-14 16:22 評論0 收藏0
LeetCode 之 JavaScript 解答第69題 —— X 的平方根（Squrt(x)）

摘要：測試用例輸入輸入輸入負數的輸入平方根為正整數的輸入平方根為小數的代碼實現寫二分查找代碼需要注意的三點循環退出條件。使用二分查找之前，判斷問題是否滿足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿題目：sqrt(x) Implement int sqrt(int x). Compute and retu...

sf_wangchong 2019-08-23 17:00 評論0 收藏0