java中怎么求一个正整数的平方根
这篇文章给大家介绍java中怎么求一个正整数的平方根,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:国际域名空间、网络空间、营销软件、网站建设、辽源网站维护、网站推广。
一、二分法
二分法的思想很简单,就是从0到N不断的去缩小范围来找一个一个满足精度的最佳值。我们举一个函数的例子:
这就是二分法的思想,求平方根也是,我们从0到value取出中间值,然后不断地比较,假设value=10,查找区间为(0,10),这时候取(0,10)的中间值mid=5,mid*mid再和value比较之后,确定下一次查找的区间变为(0,5),依次类推。一直到满足我们需要的精度即可。下面我们使用java代码实现一下:
static double MySqrt(int value, double t){
if (value < 0 || t<0)
return 0;
double left = 0;
double right = value;
double mid = (right + left) / 2;
double offset = 2*t ;
while (offset>t){
double temp = mid*mid;
if (temp > value){
right = (left + right) / 2;
offset = temp - value;
}
if (temp <= value){
left = (left + right) / 2;
offset = value - temp;
}
mid = (left + right) / 2;
}
return mid;
}
在这里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次近似值,上式称为牛顿迭代公式。
我们使用一张图来演示一下:
这种方式也很好理解。所以我们直接来看实现:
static double SqrtIterator(int value,double t){
double temp = value;
while (fabs(temp*temp-value)>t){
temp=(temp+value/temp) / 2.0;
}
return temp;
}
//取绝对值
private static double fabs(double a) {
return (a < 0) ? -a : a;
}
关于java中怎么求一个正整数的平方根就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
当前名称:java中怎么求一个正整数的平方根
本文路径:http://scyanting.com/article/pcdids.html