二分法、牛顿法求平方根

愚人节占坑。

一、二分法

简单易懂。

dichotomy.java

运行结果为:

原理为:使用二分法,不断逼近temp值,直到误差范围以内。

二、牛顿法

听名字好像很高大上,实际的程序其实很好理解。

(1)实现

Newton.java

牛顿法同样是一个不断逼近的过程。首先给出一个“结果”,用这个结果来反推,从而不断减少误差,最后求得近似值。

运行结果为:

(2)误差问题

现在把牛顿法输入的参数变一下,从15235692改为4。

运行结果为:

我们都知道4开平方就是2,但是因为求平方根的过程中允许有误差,最后算出来的只是个“逼近值”2.0000000929222947。

这好办,我们知道4开平方就是2,那么误差值肯定就是0咯?把误差范围改成0:

Newton.java

运行结果为:

这次答案变成2.0了。那么问题来了:我们知道4开平方不多不少正是整数2,才能自信地把误差值写成0。假如现在我要开15235692这个数的平方,还能这样写吗?

事实上,如果15235692不能开方出一个整数,为了让误差值小于等于0,程序就会永远逼近下去。也就是说,为了让getSquareRoot方法“通用”,误差值就不能为0,从而导致能准确开出整数方的数字(比如4)不能得到精确值。

三、算法比较

虽然二分法和牛顿法得出的结果不同,但是都在误差范围内,所以都是正解。

我们需要关注的是算法的时间复杂度,很明显牛顿法更优(二分法每次都除2,收敛速度没有牛顿法快)。

要搞清楚其中的原理需要一些数学基础。具体可以参考:

https://www.matongxue.com/madocs/205.html#/madoc

四、总结

突然发现自己把高数忘光了…

发表评论

电子邮件地址不会被公开。 必填项已用*标注