牛顿迭代
这个问题其实就是求f(x)=num – x ^ 2的零点。
已知牛顿法递推公式：Xn+1 = Xn – f(Xn)/f'(Xn).
带入f'(x) = -2x.
得：Xn+1 = Xn +(num – Xn ^ 2)/2Xn = (num + Xn ^ 2) / 2Xn = (num / Xn + Xn) / 2.
用代码表示则为num = (num + x / num) / 2.
class Solution: def mySqrt(self, x: int) -> int: if x == 0: return 0 C, x0 = float(x), float(x) while True: xi = 0.5 * (x0 + C / x0) if abs(x0 - xi) < 1e-7: break x0 = xi return int(x0)
class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ num = x while num * num > x: num = (num + x / num) / 2 return num
Original: https://www.cnblogs.com/wuxianfeng023/p/16598462.html
Author: 松勤吴老师
Title: LeetCode 69. x的平方根
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/602609/
转载文章受原作者版权保护。转载请注明原作者出处！