10开根号，如何求？

double

发布于 2022-04-06 03:50:58

1.2K00

代码可运行

文章被收录于专栏：算法channel算法channel

运行总次数：0

代码可运行

你好，我是zhenguo

这是我的第507篇原创

前几天有朋友问我，面试遇到一道题目，看似简单，但是最后没有写好。

这道题目描述简单，就是使用二分法对非负数开根号，并返回。

中午我实现了一版，截止目前测试没有发现问题。

基本实现思路是这样：

先初步确定开根号所在的一个大概区间[a,b]
然后使用二分法，逐次迭代

详细实现

下面我详细介绍下上面两个步骤。

第一步，初步确定开根号所在的一个大概区间[a,b]

其中，a,b都是整数，找到i**2大于fc的i，然后break，这样可以确定所得根号值一定位于：[i-1,i]中：

对应的代码块如下所示，其中x是输入的待开根号的数字：

# 第一步，确定a，b区间
    fc = math.ceil(x)
    for i in range(fc + 1):
        if i ** 2 >= fc:
            break
    a, b = i - 1, i
    print(f'确定的区间为[{a}-{b}]')

然后，第二步，二分法迭代。既然是迭代，就要确定迭代的终止条件，初始状态，状态转移。

其中，终止条件就是搜索的区间长度变得非常小，达到阈值，默认为0.000000001，终止迭代。

初始状态时，搜索区间为[a,b]，也就是上面第一步确定的区间。

状态转移基于二分法策略，既然是二分，也就是每迭代一次，区间长度减半。

那么问题来了，我们需要确定是选择左半区间还是选择右半区间，这个确定标准是关键。不过，在开根号这里，并不难想出来。如果我们选择左半区间，意味着解一定在区间[a,mid]中，这也就意味着：a带入到曲线中与mid带入到曲线中乘积为负值，其中曲线方程为：

# 第二步，二分法迭代
    while abs(a - b) > precision:
        mid = (a + b) / 2
        if (a ** 2 - x) * (mid ** 2 - x) < 0:
            b = mid
        else:
            a = mid
    return a

完整代码

将上面的两步综合起来，完整代码如下所示：

import math


def my_sqrt(x, precision=0.000000001):
    if x < 0:
        raise ValueError('x<0')

    # 第一步，确定a，b区间
    fc = math.ceil(x)
    for i in range(fc + 1):
        if i ** 2 >= fc:
            break
    a, b = i - 1, i
    print(f'确定的区间为[{a}-{b}]')

    # 第二步，二分法迭代
    i = 1
    while abs(a - b) > precision:
        mid = (a + b) / 2
        if (a ** 2 - x) * (mid ** 2 - x) < 0:
            b = mid
        else:
            a = mid
        print(f'第{i}次迭代后sqrt({x})等于:{a}')
        i += 1
    return a


print(my_sqrt(1.21))