当前位置: 首页 >> >>

数据结构与算法面试总结

如何使用加减乘除求出一个实数的平方根(立方根)?大体上有两种思路:二分查找法和牛顿迭代法。

二分查找法

这种方法的主要思想是:先确定解的范围,然后在此范围内不断的做二分查找,直到满足精度要求。

设输入的实数为$a$,此处假定$a$为正数

  • $a\geq 1$时,$\sqrt{a}$ 满足 $1\leq \sqrt{a}\leq a$
  • $0\leq a\leq 1$时,$\sqrt{a}$则满足$a\leq \sqrt{a}\leq 1$ 注意到两种情况的区间是相反的。接下来只需要在这个区间进行二分查找即可。

牛顿迭代法

这种方法的思想是:将此问题作为求解方程的根的问题,然后使用数值计算的方法求解。

具体说来,设输入实数为$a$,目标是求$x = \sqrt{a}$,因此求解其中的$x$也就是求解方程$x^2-a=0$的根。此方程是一个非线性方程。

非线性方程的数值求解方法有多种,上面的二分法就是一种简单的方法,而牛顿迭代法则是一个更为快速有效的求解方法。

关于牛顿法的介绍可以参见此链接

可以证明,对于常见的函数,牛顿迭代法一定收敛

Loading