基础算法六:求平方根的问题
程序员文章站
2024-02-27 19:04:21
...
求解,也是面试中经常问的一个问题。该问题有两种解法:二分法和牛顿法。
首先说二分法,首先给定个初始区间范围[0,n],因为一定是在这个范围内,然后比较这个区间的中值的平方和n,如果小于n,将范围缩小为[m,n],如果大于n,将范围缩小为[0,]。然后重复这个步骤,直到误差小于设定的阈值。
代码如下:
def binary_search(n, e=1e-5):
'''
二分法计算平方根
'''
max = n
min = 0.
mid = (max + min) / 2.
while abs(mid * mid - n) > e:
if mid * mid > n:
max = mid
elif mid * mid < n:
min = mid
else:
return mid
mid = (max + min) / 2.
return mid
然后是牛顿法,牛顿法是一种求函数的0点的方法,对于我们这个问题,如果我们要求的值为,那么,于是就转化成了求的0点。牛顿法的做法是给定的初始值,对求导求出在处的切线,该切线和y轴交点处为,将更新为,重复刚才的过程,使不断逼近的点。
如下图所示:
的更新公式推导过程为:
在处的切线方程为:
则
于是
代码如下:
def newton_search(n, e=1e-5):
'''
牛顿法计算平方根
'''
x = n
while abs(x * x - n) > e:
x = (x + n / x) / 2.
return x
运行结果如下所示:
if __name__ == '__main__':
print(binary_search(2))
print(newton_search(2))
1.414215087890625
1.4142156862745097
上一篇: 浅析python递归函数和河内塔问题
下一篇: java 中匿名内部类的实例详解