P4756 汉诺塔步数（提高）

解题思路

汉诺塔是一个非常经典的递归问题。有三根柱子 A、B、C，A 柱上从上到下放着 n 个盘子，要求全部移到 C 柱，规则是：每次只能移动一个盘子，而且大盘子永远不能压在小盘子上面。题目要求我们把每一步移动的过程都输出出来，格式是"第几步:A-C"。

怎么用递归解决呢？关键想法是"拆成三步"：

• 第一步：想办法把最上面的 n-1 个盘子从 A 柱移到 B 柱（借 C 柱当"中转站"）；
• 第二步：把最大的那个盘子从 A 柱直接移到 C 柱；
• 第三步：再把 B 柱上的 n-1 个盘子移到 C 柱（借 A 柱当"中转站"）。

你看，移动 n 个盘子的问题，被我们变成了两个移动 n-1 个盘子的小问题。每个小问题又可以继续变小，直到只剩 1 个盘子：直接把它从起点移到终点就行。

这就是递归函数 hanoi(n, from, via, to) 的写法：参数依次是"要移几个盘子、起点柱、中转柱、终点柱"。当 n == 1 时直接输出一步；否则先递归移动 n-1 个，再输出把最大盘子移走的那一步，最后再递归移动剩下 n-1 个。

我们用变量 cnt 记录现在是第几步，每输出一步就把 cnt 加 1。比如 n = 3 时，输出正好是样例里的 7 步。你会惊奇地发现，移动 n 个盘子一共需要 2^n - 1 步：3 个盘子要 7 步，4 个盘子要 15 步，n 越大步数增长得越快。

参考代码

// 汉诺塔：把A柱上n个盘子按规则全部移到C柱，输出每一步的移动过程
#include <iostream>
using namespace std;

int cnt = 0;   // 步数计数器

// 把n个盘子从from柱借助via柱移到to柱
void hanoi(int n, char from, char via, char to) {
    if (n == 1) {
        cout << ++cnt << ':' << from << '-' << to << endl;   // 只有一个盘子直接移过去
        return;
    }
    hanoi(n - 1, from, to, via);   // 先把上面n-1个盘子移到via柱
    cout << ++cnt << ':' << from << '-' << to << endl;       // 再把最大的盘子移到to柱
    hanoi(n - 1, via, from, to);   // 最后把via柱上的n-1个盘子移到to柱
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

复杂度分析

移动 n 个盘子需要 2^n - 1 步，每一行输出对应一次递归里的移动操作，所以时间复杂度和输出的行数一样，是 O(2^n)。题目保证 n ≤ 8，2^8 - 1 = 255，最多输出 255 行，非常小。递归的深度是 n 层，空间 O(n)。虽然汉诺塔的步数随 n 增长特别快（n = 64 时超过 1800 亿亿步），但题目范围小，递归完全能胜任。