题解 | #汉诺塔#

分析

假设函数 move(n, src, aux, dst) 表示把 n 个盘子从 src 移到 dst，aux 为辅助杆）：

1. 基准情形（Base Case）

   • 若 n == 1，直接输出 “src dst”（把唯一盘子从源杆移到目标杆），返回。

2. 递推情形（Recursive Case）

   • 步骤 1：move(n‑1, src, dst, aux)
     —— 把上面的 n‑1 个盘子从 src 借助 dst 移动到 aux（此时 aux 成为目标杆）。
   • 步骤 2：输出 “src dst”
     —— 把第 n 个（最底层） 大盘子从 src 直接移到 dst。
   • 步骤 3：move(n‑1, aux, src, dst)
     —— 把刚才挪到 aux 上的 n‑1 个盘子借助 src 移动到 dst。

3. 递归结束

   • 当所有递归调用返回，所有盘子的移动已经按最优顺序完成，输出序列即为所求。

说明

• 输出格式的每一行都是两个字母（如 A C），正好对应一次合法的搬动。
• 递归顺序保证大盘永远在小盘下面，从而满足题目规则。
• 若使用 迭代/非递归 方式，可采用二进制（Gray 码）或栈模拟递归的思路，但本质仍是产生同样的 2^n‑1 步移动序列。

递归实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void hanoi(int n, char src, char aux, char dst) {
    if (n == 0)
        return;
    if (n == 1) {
        cout << src << " " << dst << endl;
        return;
    }
    // move n - 1 from src to aux
    hanoi(n - 1, src, dst, aux);
    // move bottom to dst
    cout << src << " " << dst << endl;
    // move n - 1 from aux to dst
    hanoi(n - 1, aux, src, dst);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
}