解题思路

汉诺塔是经典的递归问题：要把 n 个碟子从 A 柱移到 C 柱，每次只能搬一个，大的不能压在小的上面。

怎么用递归想？

要移 n 个碟子，可以分三步：

1. 先把上面 n-1 个碟子，从 A 柱借助 C 柱移到 B 柱
2. 把最下面那个最大的碟子，从 A 柱直接移到 C 柱
3. 再把 B 柱上的 n-1 个碟子，借助 A 柱移到 C 柱

而移动 n-1 个碟子，又是同样的问题，只是柱子不一样。这就是递归：把大问题拆成同样的小问题。

递归的出口：当只剩下 1 个碟子时，直接把它从起点移到终点，不用借助别的柱子。

用一个函数 hanoi(n, a, b, c) 表示：把 n 个碟子从 a 柱移到 c 柱，b 柱是辅助。

• 出口：n==1 时，输出 a To c
• 递归：先 hanoi(n-1, a, c, b)，再输出 a To c，最后 hanoi(n-1, b, a, c)

参考代码

#include <iostream>
using namespace std;

void hanoi(int n, char a, char b, char c) {
    if (n == 1) {
        cout << a << " To " << c << endl;
        return;
    }
    // 先把前 n-1 个从 a 移到 b（借助 c）
    hanoi(n - 1, a, c, b);
    // 再把最大的从 a 移到 c
    cout << a << " To " << c << endl;
    // 最后把 n-1 个从 b 移到 c（借助 a）
    hanoi(n - 1, b, a, c);
}

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

复杂度分析

• 时间复杂度：O(2^N)，每多一个碟子，步骤数翻倍
• 空间复杂度：O(N)，递归的深度是 N