10开根号,如何求?

你好，我是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 mathdef 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 aprint(my_sqrt(1.21))

希望这篇文章对你现在或日后有帮助，欢迎点赞或收藏。

关键词： 初始状态 我们需要 那么问题来了