CSP-J 2024 第一轮 第 40 题：汉诺塔：③处应填

题目

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

③ 处应填（  ）

选项

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

答案

B

题解

答案是 B．src, tgt, tmp。

dfs(i, src, tmp, tgt) 的含义是：把 i 个圆盘从 src 移到 tgt，借助 tmp。

要移动这 i 个圆盘，需要三步：

1. 把上面的 i - 1 个圆盘从 src 移到 tmp，借助 tgt。
2. 把最下面的大圆盘从 src 移到 tgt。
3. 把 i - 1 个圆盘从 tmp 移到 tgt，借助 src。

③ 对应第一步。按函数参数的顺序“起点、辅助柱、终点”，应写成：

``cpp dfs(i - 1, src, tgt, tmp); ``

注意：tmp 虽然叫“辅助柱”，但在这次递归调用中，它是要到达的终点。