DS查找——折半查找求平方根
Description
假定输入y
是整数,我们用折半查找来找这个平方根。在从0
到y
之间必定有一个取值是y
的平方根,如果我们查找的数x
比y
的平方根小,则x^2<y
,如果我们查找的数x
比y
的平方根大,则x^2>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.493164063 | 0.493164063 |
2.1875 | 2.34375 | 2.265625 | 5.133056641 | 0.133056641 |
2.1875 | 2.265625 | 2.2265625 | … | … |
最后求得5
的平方根为2.236
温馨提示: 计算过程中为确保精确性,计算变量的类型都用double
保留小数位数请采用printf("%.3f\n",x)
?的格式输出或cout<<fixed<<setprecision(3)<<x<<endl;
程序框架参考平时练习中折半查找的方法
Input
第 1 行输入一个整数n < 100
,表示有n
个数
从第 2 行起到第n+1
行输入n
个整数
Output
输出n
个数的平方根,精确到小数点后三位。
Sample
#0
Input
Copy
2 13 5
Output
Copy
3.606 2.236
tips:有小数点限制位数的我个人都喜欢用printf
思路:
? ? ? ?还是用二分法逐渐逼近,但是结束的条件是给出的要求保留精度:比如满足|x^2-y|<0.00001
所以结束循环条件是abs(x^x-y)<0.00001
? ? ? ?还有本题跟之前的有一点区别,本题是二分答案,就是我们的mid,就是我们要得到的答案,mid满足一定条件下退出循环
? ? ? ?左边界left=0,有边界right=n,mid=(left+right)/2,如果mid满足条件,就退出循环。如果mid不满足条件且mid*mid<n,那就说明小了,left左边界就右移动到mid此时的位置。相反如果大了就right左移到mid的位置
? ? ? ?所以退出的条件是abs(mid*mid-n)<0.00001
? ??
主要代码:
全部代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
double left = 0, right = n;
double mid = (left + right) / 2;//因为不想然mid为空值所以先除了一遍
//本题用的是二分答案,mid就是我们最后得出的根号n
while (abs(mid * mid - n) >= 0.00001)//abs(mid * mid - n) < 0.00001是退出的条件,
{ //不满足条件就进入循环所以是>=
mid = (left + right) / 2;
if (mid * mid < n)
{
left = mid;//说明mid就是我们的根号n的平方<n,所以左边界向右移动
}
else
{
right = mid;说明mid就是我们的根号n的平方>=n,所以右边界向左移动
}
}
printf("%.3f\n", mid);//输出mid,mid就是我们要得到的根号n
}
return 0;
}
肯定有人觉得我在水文章。
就水就水就水,你管我!!!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!