10开根号,如何求?
Python与算法社区
共 902字，需浏览 2分钟
·
2022-04-02 21:15
你好，我是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))
希望这篇文章对你现在或日后有帮助，欢迎点赞或收藏。
评论