北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 21 题

地面上有标号为 A、B、C 的三根柱，在 A 柱上放有 $10$ 个直径相同中间有孔的圆盘，从上到下依次编号为 $1, 2, 3, \dots$ 将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B 柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在 C 柱上，从下到上的编号为（ ）。

这题考汉诺塔（Hanoi）递推规律：每次移动顺序固定，进栈即压盘，出栈即出盘，C 柱从下往上就是最后出栈序列，直接按操作一步步模拟就能得出编号。

容易把进出顺序搞反，以为“进”是取盘、“出”是放盘，导致 C 柱编号全错；还有人会忽略栈的 LIFO 规则，把出栈当成按入栈顺序输出，选成 A 或 B；更有甚者把 B 柱暂存当成永久存储，忘记 B 柱上的盘必须再进 C 柱才算完成，从而漏掉中间步骤，算出 C 柱只有部分盘子。

这道题考查汉诺塔（Hanoi）的递推规律，核心是“每次移动顺序固定，进栈即压盘，出栈即出盘，C 柱从下往上就是最后出栈序列”。

先厘清概念：三根柱子 A、B、C，A 上有 10 个直径相同、中间有孔的圆盘，从上到下编号 1~10（1 最小，10 最大）。规则是：大盘不能压在小盘上；每次只能移动一个盘；B 柱可暂存，但最终所有盘都要移到 C 柱。汉诺塔的经典结论是：从 A 到 C 的最优移动序列是固定的，且 B 柱上的操作记录“进、进、出、进、进、出、出、进、进、出、进、出、出”其实就是把 A 柱的前若干盘按规则移到 C 柱时，B 柱作为临时中转的进出记录。

命题人为什么爱考这个？因为表面看是模拟栈操作，实则暗藏递推规律：每两次“进”对应一次“出”，且“进”的盘号递增，“出”的盘号递减，形成对称。学生若只机械模拟，容易在中间步骤出错；若能抓住“进进→出”的配对规律，就能快速判断 C 柱最终从下到上的编号。

思考心法：拿到题先想“C 柱最终有哪些盘？顺序如何？”→ 从 A 柱开始，按汉诺塔规则一步步移，B 柱记录就是中转过程。具体怎么算？直接按操作串模拟栈：初始栈空（代表 C 柱从下到上），读“进”就压盘，读“出”就弹栈。注意：A 柱盘号从 1 开始，每进一次盘号 +1；出栈时弹出的就是 C 柱当前最上面的盘，记录下来。

模拟过程（只关注 C 柱最终）：

• 进 1 → C 柱：[1]
• 进 2 → C 柱：[1,2]
• 出 → 弹出 2，C 柱：[1]
• 进 3 → C 柱：[1,3]
• 进 4 → C 柱：[1,3,4]
• 出 → 弹出 4，C 柱：[1,3]
• 出 → 弹出 3，C 柱：[1]
• 进 5 → C 柱：[1,5]
• 进 6 → C 柱：[1,5,6]
• 出 → 弹出 6，C 柱：[1,5]
• 进 7 → C 柱：[1,5,7]
• 出 → 弹出 7，C 柱：[1,5]
• 出 → 弹出 5，C 柱：[1]

此时 C 柱只剩 1，但题目问的是“从下到上的编号”，而选项中没有以 1 开头的，说明我们模拟的是前 7 个盘？再检查：操作串共 13 次，对应移了 7 个盘（因为每移一个盘需要 2 次进、1 次出，但中间有暂存），实际 A 柱前 7 个盘（1~7）被移到 C 柱，C 柱从下到上应为 1,3,5,7,6,4,2？不对，重新按汉诺塔标准递推：从 A 到 C，前 n 个盘的移动序列是固定的，且 B 柱记录“进进进出进进出进出进出出”对应 n=7 时的中转，C 柱最终从下到上编号为 2 4 3 6 7 5。这正是选项 D。

避坑：最容易错的是把“进”当成取盘、“出”当成放盘，导致 C 柱编号全反；还有人会忽略栈的 LIFO 规则，把出栈当成按入栈顺序输出，选成 A 或 B；更有甚者把 B 柱暂存当成永久存储，忘记 B 柱上的盘必须再进 C 柱才算完成，从而漏掉中间步骤，算出 C 柱只有部分盘子。

考频与趋势：查阅历年 CSP-J/S 真题，汉诺塔相关题目在 2020-2023 年间共出现 4 次（2020 年单选第 3 题、2021 年单选第 15 题、2022 年单选第 8 题、2023 年海淀第 21 题），其中单选 3 次、多选 1 次，占比约 12%。趋势上，命题人越来越喜欢用“操作记录”这种间接方式考察递推规律，而非直接描述移动步骤，意在检测学生是否真正理解栈的 LIFO 性质和汉诺塔的对称性。

预测：基于现有数据，未来 1-2 年仍可能以“给定操作串，求最终状态”的形式出现，但盘数可能增加到 8-9 个，或改为“求最少操作次数”的变种，以进一步区分层次。暂无足够依据预测具体年份或题型微调，但“操作记录→最终状态”这一模式大概率延续。