2024 第一轮真题解析（三）：完善程序题

2024 年 CSP-J（入门级）第一轮认证于 2024 年 9 月 21 日举行。在前两篇文章中，我们分别解析了单项选择题和阅读程序题。

本文为您带来 CSP-J 2024 第一轮真题解析的第三部分：完善程序题（共 2 大题，每小题 3 分，共计 30 分）。

完善程序题主要考查对完整算法逻辑的理解能力以及代码填空的严谨度。2024 年入门级的两道完善程序题分别为：

1. 判断平方数：利用开方上限与循环遍历完成完全平方数的判定。
2. 汉诺塔问题：典型的递归分治算法实现。

📌 三、完善程序（单选题，每小题 3 分，共计 30 分）

📍 第一题：判断平方数

💻 题目背景与源码展示

问题描述： 给定一个正整数 $n$，希望判断这个数是否为完全平方数，即存在一个正整数 $x$，使得 $x$ 的平方为 $n$。试补全程序。

#include <iostream>
#include <vector>
using namespace std;

bool isSquare(int num) {
    int i = ____①____;
    int bound = ____②____;
    for (; i <= bound; ++i) {
        if (____③____) {
            return ____④____;
        }
    }
    return ____⑤____;
}

int main() {
    int n;
    cin >> n;
    if (isSquare(n)) {
        cout << n << " is a square number" << endl;
    } else {
        cout << n << " is not a square number" << endl;
    }
    return 0;
}

💡 算法逻辑分析

判定一个正整数 num 是否为完全平方数，最基础的思想是试除/枚举法：

• 正整数 $x$ 的最小值从 $1$ 开始试探。
• 上限 bound 取 $\lfloor\sqrt{num}\rfloor$ 即可。如果存在整数 $i \in [1, \text{bound}]$ 使得 $i \times i = num$，则 num 为完全平方数。
• 若循环结束仍未找到满足条件的 $i$，则 num 不是完全平方数。

❓ 逐题解析与选项对比

1. ① 处应填（ ）

A. 1
B. 2
C. 3
D. 4

正确答案： A

深度解析： 题目明确要求判断 $n$ 是否为正整数 $x$ 的平方。正整数从 $1$ 开始，因此循环变量 i 的初始值应设置为 1。从 $i=1$ 开始向上枚举判断。故选 A。

2. ② 处应填（ ）

A. (int)floor(sqrt(num))-1
B. (int)floor(sqrt(num))
C. floor(sqrt(num/2))-1
D. floor(sqrt(num/2))

正确答案： B

深度解析： 若 $i^2 = num$，则 $i = \sqrt{num}$。枚举 $i$ 的最大可能整数值为 $\lfloor\sqrt{num}\rfloor$。

在 C++ 中，sqrt(num) 返回浮点数，数学函数 floor() 表示向下取整（例如 $\lfloor 3.162 \rfloor = 3$）。通过向下取整并显式转换为整型 (int)floor(sqrt(num))，可以准确求出循环的上限变量 bound。因此 bound 应赋值为 (int)floor(sqrt(num))。故选 B。

3. ③ 处应填（ ）

A. num = 2 * i
B. num == 2 * i
C. num = i * i
D. num == i * i

正确答案： D

深度解析： if 条件判断需要检查当前枚举的 i 的平方是否等于 num。

• A、C 选项使用的是赋值运算符 =，而非相等比较关系运算符 ==。
• B 选项 2 * i 表示的是 2 倍而非平方。
• D 选项 num == i * i 正确判断 num 是否等于 $i^2$。故选 D。

4. ④ 处应填（本题有多个可能选项）（ ）

A. num = 2 * i
B. num == 2 * i
C. true
D. false

正确答案： A / C （官方认定选 A 或 C 均可得分）

深度解析：

• 常规逻辑（选项 C）： 当找到某个 $i$ 使得 $i^2 = num$ 时，说明 num 是完全平方数，应直接返回布尔值 true。
• 语法技巧/官方双选说明（选项 A）： 在 C++ 中，表达式 num = 2 * i 属于赋值表达式，其求值结果为赋值后的右值 2 * i。因为 $i \ge 1$，所以 2 * i > 0（非零整数）。当非零整数隐式转换为 bool 类型时，结果为 true！因此 return num = 2 * i; 效果等价于 return true;。
• 官方最终认定选项 A 与选项 C 均算作正确选项。

5. ⑤ 处应填（ ）

A. num = i * i
B. num != i * i
C. true
D. false

正确答案： D

深度解析： 若 for 循环正常结束且未在循环体内提前 return，说明在 $1 \sim \lfloor\sqrt{num}\rfloor$ 范围内没有找到任何整数 $i$ 满足 $i^2 = num$。因此该数不是完全平方数，函数应返回 false。故选 D。

📍 第二题：汉诺塔问题（Hanoi Tower）

💻 题目背景与源码展示

问题描述： 给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移动到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：

1. 只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
2. 每次只能移动一个圆盘。
3. 小圆盘必须始终在大圆盘之上。

试补全程序。

#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ____①____) {
        move(____②____);
        return;
    }
    dfs(i - 1, ____③____);
    move(src, tgt);
    dfs(____⑤____, ____④____);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
    return 0;
}

汉诺塔（Hanoi Tower）问题是理解和掌握递归（Recursion）与分治（Divide and Conquer）思想的最经典范例。

1. 如何直观理解“分治与递归”思想？

• 分治（分而治之）： 面对“把 $i$ 个盘子从柱子 A 移动到柱子 C”这个庞大复杂的问题，我们无法一步到位。但如果我们能先解决规模小一点的子问题——“把上面的 $i-1$ 个盘子挪开”，那么剩下的最大盘子就能直接一步挪到目标柱 C 上！最后再把那 $i-1$ 个盘子挪到 C 上即可。
• 递归（信任黑盒）： 理解递归最忌讳盲目“死抠”每一层递归的微观展开。正确的思维方式是 “抽象与信任”： 假设 dfs(i - 1, ...) 已经是一个绝对可靠的黑盒，它能完美、合法地帮你把 $i-1$ 个盘子移动到指定位置。我们只需关心如何利用这个黑盒组织好当前的 3 个核心步骤。

2. 函数参数的映射与“柱子角色转换”

函数声明为：void dfs(int i, char src, char tmp, char tgt)

• i：当前需要移动的盘子总数。
• src（Source，起始柱）： 当前任务中盘子所在的初始柱子。
• tmp（Temporary，中转柱/辅助柱）： 当前任务中作为临时中转放置盘子的柱子。
• tgt（Target，目标柱）： 当前任务中盘子最终要放到的柱子。

在递归调用的三步中，三根柱子的**“物理身份（A、B、C）不变”，但“逻辑角色（起始、中转、目标）在动态转换”**：

1. 第一步（把顶层 $i-1$ 个盘子挪开）：
   • 目标：将上面 $i - 1$ 个盘子从起点 src 挪到中转柱 tmp 上，此时原来的 tgt 柱充当辅助中转。
   • 角色对应：起点 src $\to$ 辅助 tgt $\to$ 目标 tmp。
   • 代码调用：dfs(i - 1, src, tgt, tmp)。
2. 第二步（移动最底层最大盘）：
   • 此时顶层 $i-1$ 个盘子已全部在 tmp 上，src 上仅剩下第 $i$ 个（最大）盘子。
   • 直接将最大盘从 src 移动到 tgt：调用 move(src, tgt)。
3. 第三步（把 $i-1$ 个盘子归位到目标柱）：
   • 目标：将暂存在 tmp 柱上的 $i - 1$ 个盘子挪到终点 tgt 上，此时原来的 src 柱充当辅助中转。
   • 角色对应：起点 tmp $\to$ 辅助 src $\to$ 目标 tgt。
   • 代码调用：dfs(i - 1, tmp, src, tgt)。

当盘子数量降到 $i = 1$ 时（递归基 / 边界条件），不需要再进行子问题拆解，直接调用 move(src, tgt) 即可完成移动并回溯。

3. 具体实例追踪（以 $n = 2$ 为例）

假设 $n = 2$，初始调用 dfs(2, 'A', 'B', 'C')（即 $i=2$, src='A', tmp='B', tgt='C'），进入分治步骤：

1. 执行第一步： 调用 dfs(1, 'A', 'C', 'B')。因为 $i == 1$，触发递归基，输出 从柱子A挪到柱子B 并返回。
2. 执行第二步： 调用 move('A', 'C')，输出 从柱子A挪到柱子C（把底层最大盘挪到 C）。
3. 执行第三步： 调用 dfs(1, 'B', 'A', 'C')。因为 $i == 1$，触发递归基，输出 从柱子B挪到柱子C 并返回。

最终执行步骤（共 3 步）：

1. 从柱子A挪到柱子B
2. 从柱子A挪到柱子C
3. 从柱子B挪到柱子C

（对于任意 $n$ 个盘子，总移动步数为 $2^n - 1$ 次，时间复杂度为 $O(2^n)$。）

❓ 逐题解析与选项对比

1. ① 处应填（ ）

A. 0
B. 1
C. 2
D. 3

正确答案： B

深度解析： 根据递归基的设定： 当要移动的盘子数量 $i == 1$ 时，只需执行一次移动 move(...) 并直接返回，不需要再进行后续的分治拆解。 因此递归终止条件（边界情况）为 $i == 1$。故①处应填 1，选 B。

2. ② 处应填（ ）

A. src, tmp
B. src, tgt
C. tmp, tgt
D. tgt, tmp

正确答案： B

深度解析： 当 $i == 1$ 时，唯一的盘子需要直接从源柱子 src 移动到目标柱子 tgt。 函数 move 的参数列表为 move(char src, char tgt)，因此传入 src, tgt。故选 B。

3. ③ 处应填（ ）

A. src, tmp, tgt
B. src, tgt, tmp
C. tgt, tmp, src
D. tgt, src, tmp

正确答案： B

深度解析： 根据汉诺塔分治核心思想，要把 $i$ 个盘子从 src 移到 tgt： 第一步需要把上面的 $i - 1$ 个盘子从源柱子 src 移动到中转辅助柱 tmp，而此时的目标柱子 tgt 作为中转站。 dfs 函数的形参定义为 dfs(int i, char src, char tmp, char tgt)，即第一个参数为盘数，第二个为起点，第三个为辅助点，第四个为终点。 因此要把 $i-1$ 个盘子从 src 借助 tgt 移到 tmp，实参应顺序传入 src, tgt, tmp。故选 B。

4. ④ 处应填（ ）

A. src, tmp, tgt
B. tmp, src, tgt
C. src, tgt, tmp
D. tgt, src, tmp

正确答案： B

深度解析： 在第 15 行完成最底盘 move(src, tgt) 后，第三步需要把留在中转柱 tmp 上的 $i - 1$ 个盘子从 tmp 移动到目标柱 tgt，此时 src 作为辅助柱。 对应 dfs 的形参顺序 (起点, 辅助点, 终点)，起点为 tmp，辅助点为 src，终点为 tgt。 因此④处实参应为 tmp, src, tgt。故选 B。

5. ⑤ 处应填（ ）

A. 0
B. 1
C. i - 1
D. i

正确答案： C

深度解析： 第三步要移动的是之前暂存在 tmp 柱上的 $i - 1$ 个盘子，因此盘数参数必须为 i - 1。故选 C。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号