CSP-J 2022 第一轮 第 30 题：程序（三）：k增大第二个数是否总会变成1

题目

1  #include <iostream>
2
3  using namespace std;
4
5  int n,k;
6
7  int solve1()
8  {
9      int l = 0, r = n;
10     while(l <= r){
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17
18 double solve2(double x)
19 {
20         if (x == 0) return x;
21         for (int i = 0; i < k; i++)
22             x = (x + n / x) / 2;
23     return x;
24 }
25
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

对于任意输入的 $n$，随着所输入 $k$ 的增大，输出的第二个数会变成 $1$。

选项

• A. 正确
• B. 错误

答案

B

题解

答案是 B. 错误。

这段程序分两步求平方根：

1. solve1() 用二分查找，得到 $\lfloor\sqrt n\rfloor$。
2. solve2() 不断执行

$$ x\leftarrow\frac{x+n/x}{2}, $$ 这是求平方根的牛顿迭代法，通常会让结果越来越接近 $\sqrt n$。

但第 30 行判断的是： ``cpp ans * ans == n `` 它要求完全相等，并不是“足够接近”。

例如 n = 2 时，$\sqrt2$ 无法用 double 精确表示。在通常的双精度浮点运算中，迭代最终会停留在一个近似值上，它的平方仍不等于 2，输出的第二个数仍为 0。继续增大 k 也不能消除这种表示误差。

因此，迭代次数增多不保证浮点数的精确相等判断成立。