CSP-J 2022 第一轮 第 32 题：程序（三）：输入2 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 表示范围的自然数，完成下面的判断题和单选题：

当输入为 2 1 时，输出的第一个数最接近（ ）。

选项

• A. $1$
• B. $1.414$
• C. $1.5$
• D. $2$

答案

C

题解

答案是 C．\(1.5\)。

输入 2 1，即 n = 2、k = 1，程序分两步计算：

1. solve1() 返回 1

它用二分查找，找到满足 \(x^2 \le n\) 的最大整数，也就是 \(\lfloor\sqrt n\rfloor\)。

因为 \(1^2 \le 2 < 2^2\)，所以返回 1。

1. solve2(1) 返回 1.5

x 初始为 1。因为 k = 1，循环只执行一次： \[ x=\frac{x+n/x}{2} =\frac{1+2/1}{2} =1.5 \]

因此，输出的第一个数为 1.5，选 C。

注意：虽然这段程序在近似计算 \(\sqrt2\)，但这里只迭代了一次，不能直接选 \(1.414\)。