CSP-J 入门级 · CSP 2024 入门级第一轮 第 20 题

第 2 题

（汉诺塔问题） 给定三根柱子，分别标记为 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');
}

1. ① 处应填（ ） A. 0 B. 1 C. 2 D. 3 2. ② 处应填（ ） A. src, tmp B. src, tgt C. tmp, tgt D. tgt, tmp 3. ③ 处应填（ ） A. src, tmp, tgt B. src, tgt, tmp C. tgt, tmp, src D. tgt, src, tmp 4. ④ 处应填（ ） A. src, tmp, tgt

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

拿到汉诺塔题，别急着套公式，先想递归的‘分治’逻辑：把n个盘子拆成‘上面n-1个’和‘最底下那个’，先让上面那堆借助中间柱子挪走，再挪最大的，最后把上面那堆挪回来。代码里就是填这几个步骤的参数和终止条件。

最容易栽跟头的地方是递归调用的参数顺序，尤其是③和④。很多同学会把‘源、中转、目标’搞混，比如把③填成src,tmp,tgt，结果程序逻辑就全乱了：本来是要把n-1个盘子从src借tgt挪到tmp，结果却写成从src借tmp挪到tgt，这完全违背了汉诺塔‘小盘压大盘’的规则，导致无法完成移动。还有⑤处，递归深度要减1，写成i就死循环了。另外，①处终止条件填0也是常见错误，因为题目保证n>=1，i=0永远不会触发，程序会一直往下递归直到栈溢出。

这道题考的是汉诺塔问题的递归解法，核心就是‘分治’思想：把大问题拆成三个小问题——先移上面n-1个，再移最大的那个，最后移剩下的n-1个。代码里的dfs函数就是实现这个逻辑的骨架，我们需要补全的是递归的终止条件、移动动作以及两次递归调用的参数顺序。

概念梳理：汉诺塔有三根柱子，A是源，C是目标，B是中转。规则很死：每次只能动最上面的盘子，小盘必须在大盘上面。递归的关键在于，要把n个盘子从src移到tgt，借助tmp，可以分解为三步： 1. 把上面n-1个盘子从src移到tmp（此时tgt暂时当中转）； 2. 把剩下的那个最大的盘子从src直接移到tgt； 3. 把tmp上的n-1个盘子移到tgt（此时src暂时当中转）。

逐空推演：

先看①处，这是递归的终止条件。题目要求把i个盘子移完就返回。如果i=1，说明只剩一个盘子，直接移动即可，不需要再递归。如果填0，那对于任何n>=1的情况，i永远不会等于0，程序会无限递归下去直到栈溢出。所以①必须填1（选项B）。

接着看②处，当i==1时，直接调用move函数。move的参数是源柱子和目标柱子。此时我们只有一个盘子，它就在src上，要移到tgt上，所以填src, tgt（选项B）。

再看③处，这是第一次递归调用。我们要把上面i-1个盘子从src移到tmp，这时候tgt充当中转柱。函数签名是dfs(i, src, tmp, tgt)，所以调用时要把参数对应起来：i减1，源是src，中转是tgt，目标是tmp。也就是dfs(i-1, src, tgt, tmp)（选项B）。很多同学容易在这里把tmp和tgt的位置搞反，填成src,tmp,tgt，那逻辑就错了，因为那样tmp变成了目标，tgt变成了中转，完全违背了汉诺塔的步骤。

然后看⑤处，这是第二次递归调用的第一个参数，代表要移动的盘子数量。因为最大的那个盘子已经移走了，剩下的还是i-1个，所以填i-1（选项C）。这里千万别填i，否则死循环。

最后看④处，这是第二次递归调用的参数。我们要把tmp上的i-1个盘子移到tgt，这时候src充当中转。对应函数签名，源是tmp，中转是src，目标是tgt。也就是dfs(i-1, tmp, src, tgt)（选项B）。这里参数顺序是tmp, src, tgt，对应选项B。

完整流程验证：

• 当n=1时，dfs(1, A, B, C) -> i==1成立，直接move(A,C)，正确。
• 当n=2时，dfs(2, A, B, C) -> i!=1，先dfs(1, A, C, B)把A上的1个移到B，再move(A,C)把A上的第2个移到C，最后dfs(1, B, A, C)把B上的1个移到C。结果A空了，C上有两个，顺序正确。
• 当n=3时，逻辑同理，先移2个到B，再移1个到C，最后把B上的2个移到C。完美符合汉诺塔规则。

命题人视角：这题属于基础递归题，但参数顺序是经典坑点。命题人故意把tmp和tgt在递归调用中的位置打乱，考察你是否真正理解汉诺塔的三步走逻辑，而不是死记硬背代码。如果只背了‘把n-1移到tmp’，却不注意tmp和tgt的对应关系，就会在③处填错。

考频与趋势：递归函数在题库中非常高频，共考过115题，覆盖从2007年到2026年的所有级别，尤其是2024年考了25题，2025年15题，2026年18题，说明近四年是递归的高发期。汉诺塔作为递归的‘Hello World’，虽然基础，但每年必现。DFS（深度优先搜索）也考了61题，其中2024年13题、2025年9题、2026年22题，趋势明显是逐年增加。这说明算法基础题在入门级和普及级越来越受重视，不再局限于简单的排序或循环，而是开始考察递归思维和搜索框架。

预测：基于2024-2026年的数据，递归和DFS的考频持续走高，且题目难度有从纯概念验证向结合具体场景（如迷宫、树遍历）发展的趋势。未来可能会在汉诺塔的基础上，增加变种，比如多柱子问题、带权重的移动代价，或者结合动态规划。但就汉诺塔本身而言，只要掌握‘分治三步走’和参数对应，就能稳拿分。