首页 > 其他 > 详细

DS查找——折半查找求平方根

时间:2020-01-12 17:37:39      阅读:92      评论:0      收藏:0      [点我收藏+]

题目描述

假定输入y是整数,我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根,如果我们查找的数xy的平方根小,则x2<y,如果我们查找的数xy的平方根大,则x2>y,我们可以据此缩小查找范围,当我们查找的数足够准确时(比如满足|x2-y|<0.00001),就可以认为找到了y的平方根。
 
比如求5的平方根x,则x一定满足   0<=x<=5,取x为(5+0)/2=2.5,因为2.5的平方为6.25>5,所以x一定小于2.5,也即x满足0<=x<=2.5,取x为1.25,以此类推
 
X的范围 X的取值 x2 x2-y
0 5 2.5 6.25 1.25
0 2.5 1.25 1.5625 -3.4375
1.25 2.5 1.875 3.515625 -1.484375
1.875 2.5 2.1875 4.78515625 -0.21484375
2.1875 2.5 2.34375 5.4931640625 0.4931640625
2.1875 2.34375 2.265625 5.133056640625 0.133056640625
2.1875 2.265625 2.2265625
         
         
         
         
 
最后求得5的平方根为2.236
 
 
技术分享图片温馨提示: 计算过程中为确保精确性,计算变量的类型都用double
保留小数位数请采用printf("%.3lf\n",x) 的格式输出技术分享图片

程序框架参考平时练习中折半查找的方法

输入

第1行输入一个整数n(<100),表示有n个数
从第2行起到第n+1行输入n个整数

 

输出

输出n个数的平方根,精确到小数点后三位。

样例输入

2 13 5

样例输出

3.606 2.236

提示

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
#define exc 0.00001
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        double y;
        cin>>y;
        double minn=0;
        double maxx=y;
        double a=(minn+maxx)/2;
        while(fabs(a*a-y)>=exc)
        {
            if(a*a>y)
            {
                maxx=a;
                a=(minn+maxx)/2;
            }
            else if(a*a<y)
            {
                minn=a;
                a=(minn+maxx)/2;
            }
        }
        cout<<fixed<<setprecision(3)<<a<<endl;
    }
    return 0;
}

DS查找——折半查找求平方根

原文:https://www.cnblogs.com/SZU-DS-wys/p/12182963.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!