假定输入
y
是整数,我们用折半查找来找这个平方根。在从0到y
之间必定有一个取值是y
的平方根,如果我们查找的数x
比y
的平方根小,则x2<y,如果我们查找的数x
比y
的平方根大,则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) 的格式输出
程序框架参考平时练习中折半查找的方法