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

2023-12-13 06:20:11

Description

假定输入y是整数,我们用折半查找来找这个平方根。在从0y之间必定有一个取值是y的平方根,如果我们查找的数xy的平方根小,则x^2<y,如果我们查找的数xy的平方根大,则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,取x1.25,以此类推

X的范围X的取值x2x2-y
052.56.251.25
02.51.251.5625-3.4375
1.252.51.8753.515625-1.484375
1.8752.52.18754.78515625-0.21484375
2.18752.52.343755.4931640630.493164063
2.18752.343752.2656255.1330566410.133056641
2.18752.2656252.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;
}

肯定有人觉得我在水文章。
就水就水就水,你管我!!!

文章来源:https://blog.csdn.net/weixin_74790320/article/details/134961158
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。