2种方法求解根号2

2024-06-06 13:34| 来源: 网络整理| 查看: 265

文章目录前言一、牛顿-拉弗森法（Newton-Raphson Method）二、二分查找法（Binary Search）1.算法原理2.Python实现三、两种算法的效率比较总结

前言

这是一道经典的面试题：自己编写函数实现根号2（根号n）的求解。（说明：笔者习惯使用python编程，因此以下算法实现均使用python）首先，python内置的math（数学运算）库中包含了求非负实数平方根的函数sqrt (square root)：

from math import sqrt print(sqrt(2))

可以得到一个高精度的结果，具体精度取决于操作系统限制。在笔者的64位Windows系统中，输出的结果为 1.4142135623730951

这已经是令人满意的答案了，但有没有数学方法，可以不依赖内置库函数，自己实现平方根的计算（精确估计）呢？我们来看两种方法。

一、牛顿-拉弗森法（Newton-Raphson Method）

这个方法被认为同时被艾萨克·牛顿和约瑟夫·拉弗森提出，所以被命名为牛顿-拉弗森法。

这个方法主要讲的是这个结论：如果存在一个k是多项式P的根的有效近似，那么k - p(k) / p’(k)就是一个更有效的近似值。其中p’是p的一次导数。

求解根号n可以转化为求多项式x ^ 2 - n的根的问题，该多项式的一次导数是2x. 因此，如果当前的猜测是k, 那么可以选择k - (k ^ 2 - n) / 2k 作为下一个猜测值，直到误差（k ^ 2 - n）的绝对值小于给定的值epsilon. 这种方法称为逐次逼近。

Python实现：

# 利用牛顿-拉弗森法寻找平方根 # 寻找x,满足x ^ 2 - k 在 (0, epsilon)范围内 def newton_raphson(k, epsilon): guess = k while abs(guess * guess - k) >= epsilon: guess = guess - (((guess * guess) - k) / (guess * 2)) return guess print(newton_raphson(2, 0.000000001)) 二、二分查找法（Binary Search） 1.算法原理

如果x是大于1的数，则根号x一定位于0到x之间，此时我们用（暴力的）二分查找法求根号x的近似值，判定迭代结束的条件为abs(ans ^ 2 - x) < epsilon.

如果x是小于1大于0的数，则根号x位于0到1之间，此时我们在（0，1）区间内用二分查找法求解根号x的近似值，迭代结束的条件同上。

2.Python实现

注意由于没有事先判定x的范围，所以查找上限变成了max(1.0, x). 下限为0.

# 使用二分查找求近似平方根 def bi_search_root(x, epsilon): low = 0.0 high = max(1.0, x) ans = (high + low) / 2.0 while abs(ans ** 2 - x) >= epsilon: if ans ** 2 = epsilon: guess = guess - (((guess * guess) - k) / (guess * 2)) times += 1 return guess, times print(newton_raphson(2, 0.000000001))

times变量用于记录迭代求解的总次数。这里和以下的二分查找法的epsilon参数均设置为0.000000001. 将二分查找法的代码修改为：

# 使用二分查找求近似平方根 def bi_search_root(x, epsilon): numGuesses = 0 low = 0.0 high = max(1.0, x) ans = (high + low) / 2.0 while abs(ans ** 2 - x) >= epsilon: numGuesses += 1 if ans ** 2

【本文地址】

公司简介

联系我们