Question 42
⑤ 的盘子数量
在汉诺塔程序中，⑤ 处应填什么？
正确答案
C. i - 1
一句话考点
两次递归都处理的是“去掉最大盘子后剩下的 i - 1 个小盘子”。
Shared Context
完善程序（2）汉诺塔
汉诺塔是递归入门的经典模型，空位考查递归终止条件和三个柱子的角色转换。
基础模型
`dfs(i, src, tmp, tgt)` 的含义是：把 i 个盘子从 src 移到 tgt，tmp 作为辅助柱。
终止条件
当只剩 1 个盘子时，直接从源柱挪到目标柱，不再继续拆分。
参数变换
第一次递归的目标是把前 i - 1 个盘子移到临时柱，第二次递归才是把它们移到最终目标柱。
cpp
共享程序片段#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');
}题组阅读提醒
把 n 个盘子从 A 移到 C，需要先把前 n - 1 个从 A 借助 C 移到 B，再把最大的盘子从 A 移到 C，最后把前 n - 1 个从 B 借助 A 移到 C。
三根柱子在两次递归中的身份不同，很多同学会把临时柱和目标柱的位置写反，这正是本组题的主要陷阱。
Prompt
题目与选项
在汉诺塔程序中，⑤ 处应填什么？
A. 0
B. 1
C. i - 1
D. i
Quick Check
做题抓手
先判断题型
先确定这行代码在整体算法中的职责，再看四个选项谁能完成这个职责。
再核对边界
第一轮很爱在闭区间、下标偏移、递归终止条件和布尔返回值上设陷阱。
最后看输出层次
尤其是阅读程序题，要分清函数返回值、变量值和最终打印值是不是同一件事。
Explanation
详细讲解
Step 1
汉诺塔递归的拆分方式始终是：先处理上面的 `i - 1` 个盘子，再移动最大的一个盘子，再处理那 `i - 1` 个盘子。
Step 2
因此第二次递归处理的盘子数量仍然是 `i - 1`，不是 1、更不是 i。
Step 3
所以 ⑤ 应填 `i - 1`，选 C。
Pitfalls
易错点
- 看到已经移动了一个盘子，就误以为剩下的是 1 个。
- 把问题规模原封不动写成 i，没有体现递归拆分。
Extend
拓展补充
- 经典递归模板里，规模通常会递减成 `n - 1`、`n / 2` 等形式；如果规模不变，往往就会无限递归。
返回总览
回到整套试卷
返回题目总览页，继续从目录、知识图谱或其他分区进入。
所属分区
返回 完善程序
回到首页对应分区，继续顺序刷题或查看同类知识点。
上一题
第 41 题
④ 的第二次递归参数
下一题
已经是最后一题