网站怎么添加友情链接,做免费网站安全吗,做网站开发的电话销售话术,安卓搭建网站Description
假定输入y是整数#xff0c;我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根#xff0c;如果我们查找的数x比y的平方根小#xff0c;则x2y#xff0c;如果我们查找的数x比y的平方根大#xff0c;则x2y#xff0c;我们可以据此…Description
假定输入y是整数我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根如果我们查找的数x比y的平方根小则x2y如果我们查找的数x比y的平方根大则x2y我们可以据此缩小查找范围当我们查找的数足够准确时比如满足|x2-y|0.00001就可以认为找到了y的平方根。
比如求5的平方根x则x一定满足 0x5取x为(50)/22.5因为2.5的平方为6.255所以x一定小于2.5也即x满足0x2.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) 的格式输出或coutfixedsetprecision(3)xendl;
程序框架参考平时练习中折半查找的方法
Input
第 1 行输入一个整数n 100表示有n个数
从第 2 行起到第n1行输入n个整数
Output
输出n个数的平方根精确到小数点后三位。
Sample
#0
Input
2
13
5Output
3.606
2.236AC代码
#includeiostream
#includecstring
#includealgorithm
#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;
}
