java开方语句(如何使用java语言求一个正整数的平方根)

今天的这篇文章是我在刷算法题的时候遇到的,最简单的方法是直接调用java里面的Sqrt函数,不过有时候题目中会要求我们不能使用库函数,所以在这里我们自己定义Sqrt方法。

最常见的思路有两种,第一种是二分法,第二种是牛顿的微积分思想。没错,想当年大学时候学了很久很痛苦的微积分,被我第一次派上用场了。对于这两种方法我们一个一个看。

一、二分法

二分法的思想很简单,就是从0到N不断的去缩小范围来找一个一个满足精度的最佳值。我们举一个函数的例子:

java开方语句(如何使用java语言求一个正整数的平方根)(1)

这就是二分法的思想,求平方根也是,我们从0到value取出中间值,然后不断地比较,假设value=10,查找区间为(0,10),这时候取(0,10)的中间值mid=5,mid*mid再和value比较之后,确定下一次查找的区间变为(0,5),依此类推。一直到满足我们需要的精度即可。下面我们使用java代码实现一下:

java开方语句(如何使用java语言求一个正整数的平方根)(2)

在这里value就是我们要求的数字,t表示的是精度。这个方法在这,大家可以测试一遍。不过在这里有一个小小的问题需要我们去注意:

如果我们对整数9取平方根,结果不是3,这里有精度损失,损失的原因之一是和计算机有关的,因为计算机的底层其实只有0和1,所以会无限的接近,而不能精确表示。

以上就是二分法求解的思想,这个思想很简单,不过实现的方法却是有一点点麻烦。在这里我们开始介绍第二种方法,那就是牛顿的微积分思想

二、牛顿迭代法

牛顿的微积分的思想就是无限接近,在这里提一句,如果你是数学大佬就不要追究思想到底是啥了。对于求平方根来说,使用切线来无限逼近的方式有时候能起到意想不到的效果。

设r是f(x) = 0的根,选取x0作为r初始近似值,过点(x0,f(x0))做曲线y = f(x)的切线L,L的方程为y = f(x0) f'(x0)(x-x0),求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0),称x1为r的一次近似值。过点(x1,f(x1))做曲线y = f(x)的切线,并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1),称x2为r的二次近似值。重复以上过程,得r的近似值序列,其中x(n 1)=x(n)-f(x(n))/f'(x(n)),称为r的n 1次近似值,上式称为牛顿迭代公式。

我们使用一张图来演示一下:

java开方语句(如何使用java语言求一个正整数的平方根)(3)

这种方式也很好理解。所以我们直接来看实现:

java开方语句(如何使用java语言求一个正整数的平方根)(4)

上面的方法同样可以表示。而且我们可以看到,牛顿的这个方法其实更加的简单。而且精度也更好。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页