P4740 汉诺塔（基础）

解题思路

汉诺塔的玩法：有三根柱子 A、B、C，A 柱上从下到上放着 n 个大小不一的盘子（大的在下，小的在上）。每次只能移动一个盘子，而且大盘子不能压在小盘子上面。目标是把所有盘子从 A 移到 C。

我们可以把问题想成三步：如果想移动 n 个盘子从 A 到 C，可以先把上面的 n-1 个盘子从 A 移到 B（把 B 当作中转），再把最下面最大的盘子从 A 直接移到 C，最后把这 n-1 个盘子从 B 移到 C。这样，移动 n 个盘子的问题，就变成了两次移动 n-1 个盘子的问题，这就是递归！

用函数 h(n, a, c, b) 表示：把 n 个盘子从柱子 a 移到柱子 c，借用柱子 b。递归的过程就是：

1. h(n-1, a, b, c)：先把上面 n-1 个盘子搬到中间柱 b；
2. 直接输出 a-c，把最下面的大盘子搬到目标柱 c；
3. h(n-1, b, c, a)：再把 b 上的 n-1 个盘子搬到 c。

当 n=1 时，只有一个盘子，直接输出 a-c 就可以，这就是递归的出口。以 n=3 为例，输出为：A-C、A-B、C-B、A-C、B-A、B-C、A-C，一共 7 步，正好是 2^3-1。注意题目要求输出格式是"A-C"这样的写法，中间用减号连接。

边界情况：n 最小是 1，直接输出 A-C；n 最大是 8，最多移动 2^8-1=255 步，不会超出时间限制。

参考代码

// 汉诺塔：递归输出从A移到C的每一步
#include <iostream>

void h(int n, char a, char c, char b) {
    if (n == 1) {
        std::cout << a << "-" << c << "\n";
        return;
    }
    h(n - 1, a, b, c);
    std::cout << a << "-" << c << "\n";
    h(n - 1, b, c, a);
}

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

复杂度分析

每次递归都会把规模从 n 变成 n-1，并且要调用两次自己。移动次数满足递推式 T(n)=2×T(n-1)+1，也就是 T(n)=2^n-1。所以时间复杂度是 O(2^n)。当 n=8 时，最多执行 255 次输出，速度非常快。空间上，递归最多嵌套 n 层，是 O(n) 的栈空间，也很小。因为 n 只有 8，这个指数级复杂度完全够用，小朋友可以放心使用。