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

2
13
5

Output

3.606
2.236

AC代碼

#include<iostream>
#include<cstring>
#include<algorithm>
#include <iomanip>
using namespace std;
const int N = 10010;
int arr[N];bool check(double x,double target)
{return x * x > target;
}double BinarySearch(double target, double l, double r)
{const double eps = 1e-6;   // eps 表示精度，取決于題目對精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid,target)) r = mid;//check函數判斷是否滿足條件else l = mid;}return l;
}int main()
{int t;cin >> t;while (t--) {double x;cin >> x;cout << fixed << setprecision(3) << BinarySearch(x,0,x) << endl;}return 0;
}