C / C++ / 系统课时

用递归解决汉诺塔问题

用递归解决汉诺塔问题

汉诺塔的难点不是移动一块盘,而是把“移动 n 块盘”重新表达成更小的同类问题。本课从三步拆分出发,实现可运行的 C 程序,并用调用顺序理解递归为什么能生成完整移动方案。

学习目标

  • 把汉诺塔问题拆成两个规模为 n - 1 的递归子问题
  • 写出带明确终止条件的 C 语言递归实现
  • 根据递推关系判断移动次数和递归栈深度

把移动 n 块盘拆成三步

设有源柱 A、辅助柱 B 和目标柱 C,盘子从小到大叠放,且任何时刻都不能把大盘放在小盘上。要把 n 块盘从 A 移到 C,核心不是直接决定每一步,而是完成三个阶段:

  1. 把上面的 n - 1 块盘从 A 移到 B,此时借助 C。
  2. 把最大的第 n 块盘从 A 移到 C。
  3. 把 n - 1 块盘从 B 移到 C,此时借助 A。

第 1 步和第 3 步与原问题结构完全相同,只是盘子数量少了一块、三根柱子的角色发生了变化。当 n == 1 时,只需把唯一一块盘直接移动到目标柱,这就是终止条件。

汉诺塔递归拆分为两个子问题与一次关键移动

用 C 语言实现递归移动

下面的程序把三根柱子作为字符参数传入。参数顺序固定为“源柱、辅助柱、目标柱”,这样每次递归只需要重新排列柱子的角色。

c
#include <stdio.h>

void hanoi(int n, char from, char auxiliary, char to) {
    if (n == 1) {
        printf("move disk 1: %c -> %c\n", from, to);
        return;
    }

    // 先把上面的 n-1 块移到辅助柱,为最大盘腾出路径。
    hanoi(n - 1, from, to, auxiliary);

    printf("move disk %d: %c -> %c\n", n, from, to);

    // 再把 n-1 块从辅助柱移到目标柱。
    hanoi(n - 1, auxiliary, from, to);
}

int main(void) {
    int n = 3;

    if (n <= 0) {
        printf("n must be positive\n");
        return 1;
    }

    hanoi(n, 'A', 'B', 'C');
    return 0;
}

预期输出

text
move disk 1: A -> C
move disk 2: A -> B
move disk 1: C -> B
move disk 3: A -> C
move disk 1: B -> A
move disk 2: B -> C
move disk 1: A -> C

这 7 行不是预先写好的移动表,而是递归调用在返回过程中自然产生的执行顺序。若把 n 改成其他正整数,程序会按照同一规则生成新的合法方案。

跟踪 n 等于 3 时的执行过程

第一次调用 hanoi(3, 'A', 'B', 'C') 不会立刻移动第 3 块盘,而是先进入 hanoi(2, 'A', 'C', 'B')。这个调用又会继续处理 1 块盘,直到 n == 1 才执行第一条实际移动。

最内层调用返回后,程序回到上一层,移动第 2 块盘,再完成另一侧的 1 块盘子问题。等左半部分全部结束,最外层调用才移动第 3 块盘,然后用同样方式完成右半部分。

理解这段过程时,可以把每次调用看成一句承诺:“我负责把这 n 块盘搬到目标柱,但我要先让一个更小的问题替我腾出空间。”递归函数只需要保证这一层的三阶段顺序正确,不必一次性记住所有移动步骤。

移动次数和栈空间

设移动 n 块盘需要 T(n) 次操作。前后两个子问题各需要 T(n - 1) 次,中间再移动一次最大盘,因此有:

T(n)=2T(n−1)+1T(n) = 2T(n - 1) + 1

并且 T(1) = 1,可得 T(n) = 2^n - 1。所以 n = 3 时是 7 次,n = 4 时是 15 次。时间复杂度为 O(2^n),盘子数量每增加 1,移动次数几乎翻倍。

递归调用的最大深度只沿一条子问题链从 n 下降到 1,因此额外栈空间是 O(n)。这说明汉诺塔非常适合练习递归结构,但不适合把很大的 n 当作高效求解任务。

关键判断始终是两点:基本情况 n == 1 能够到达,并且每次递归都把规模从 n 缩小到 n - 1。只要这两个条件成立,三步拆分就能完整覆盖所有合法移动。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用递归解决汉诺塔问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通