两种方法求解平方根 -- 牛顿法、二分法

2023-12-31 23:29:15

Leetcode相关题目:
69. x 的平方根

牛顿法 迭代公式:

以求解 a a a 的平方根为例,可转换为求解方程 f ( x ) f(x) f(x)的根。 f ( x ) = x 2 ? a f(x)=x^2-a f(x)=x2?a

迭代公式如下: x n + 1 = x n ? f ( x n ) f ′ ( x n ) x_{n+1} = x_n - \frac {f(x_n)}{f'(x_n)} xn+1?=xn??f(xn?)f(xn?)?

代入 f ( x ) f(x) f(x) 得:
x n + 1 = x n ? x n 2 ? a 2 ? x n = x n + a / x n 2 x_{n+1} = x_n - \frac {x_n^2-a}{2*x_n} = \frac{x_n+a/x_n}{2} xn+1?=xn??2?xn?xn2??a?=2xn?+a/xn??

停止条件为: ∣ x n + 1 ? x n ∣ < ? |x_{n+1} - x_n| < \epsilon xn+1??xn?<?
在这里插入图片描述


class MySqrt:
    """
    69. x 的平方根
    https://leetcode.cn/problems/sqrtx/description/
    """

    def solution1(self, x: int) -> int:
        """
        牛顿迭代法,递归
        :param x:
        :return:
        """
        self.a = x
        if x == 0:
            return 0
        return int(self.sqrts(x))

    def sqrts(self, x: float):
        res = (x + self.a / x) / 2
        if res == x:
            return x
        else:
            return self.sqrts(res)

    def solution2(self, a: int) -> int:
        """
        牛顿法,迭代
        :param a:
        :return:
        """
        if a == 0:
            return 0

        x = float(a)
        while (x + a / x) / 2 != x:
            x = (x + a / x) / 2

        return int(x)

    def solution3(self, x: int) -> int:
        """
        二分法
        :param a:
        :return:
        """
        l, r, ans = 0, x, -1
        while l <= r:
            mid = l + (r - l) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1

        return ans

文章来源:https://blog.csdn.net/qq_32275289/article/details/135320092
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。