《Hello 算法》分治专题：汉诺塔问题如何用"分而治之"优雅求解

本篇以《Hello 算法》分治与递归章节的汉诺塔问题为核心，从问题建模出发，演示如何把规模为 $n$ 的汉诺塔问题递归分解为 $n-1$ 与 $1$ 两档子问题，并结合仓库中 16 种语言的源码实现分析其"分解—求解—合并"的完整流程。读完你将掌握汉诺塔问题的分治推演方法、dfs(i, src, buf, tar) 递归函数的设计思路，以及 $O(2^n)$ 时间、$O(n)$ 空间的复杂度来源。

汉诺塔问题：一个与归并排序不同的分解策略

在前面的章节中，无论是归并排序还是构建二叉树，我们习惯性地把原问题平均分成两个规模为原问题一半的子问题。然而汉诺塔（Tower of Hanoi）问题采用的是一种迥然不同的分解策略，它为理解分治法的"非对称拆分"提供了绝佳案例。

问题定义与三条规则

问题：给定三根柱子 A、B、C，初始状态下柱 A 上自下而上叠放着 $n$ 个圆盘（大的在下、小的在上）。任务是把 $n$ 个圆盘整体移动到柱 C，并保持原有顺序不变。移动时必须遵守：

1. 圆盘只能从一根柱子的顶部取出，放入另一根柱子的顶部；
2. 每次只能移动一个圆盘；
3. 小圆盘必须始终位于大圆盘之上。

为了后续表述简洁，约定把规模为 $i$ 的汉诺塔问题记作 $f(i)$。例如 $f(3)$ 表示"把 $3$ 个圆盘从 A 移动到 C"。可以看到，虽然问题规则看似简单，但圆盘数量的增长会令状态空间爆炸式膨胀，这正是它值得用分治思想求解的原因。

从最简单的情形入手：$f(1)$ 与 $f(2)$

$f(1)$：无需借用任何柱子

当只有 $1$ 个圆盘时，它既是最大的也是最小的圆盘，直接从 A 顶部移动到 C 顶部即可完成，一次移动就得到最优解。$f(1)$ 由此成为递归的"基本情形（base case）"，它是整个分治过程的天然出口。

$f(2)$：首次引入"缓冲柱"

当有 $2$ 个圆盘时，如果直接把上面的小盘放到 C，随后的大盘会违反"小盘必须在大盘之上"的约束。因此必须借助柱子 B 完成中转，标准三步走为：

1. 先将上面的小圆盘从 A 移动到 B；
2. 再将下面的大圆盘从 A 直接移动到 C；
3. 最后将小圆盘从 B 移动到 C。

这个求解过程可概括为：把两个圆盘借助 B 从 A 移至 C。其中 C 称为目标柱，B 称为缓冲柱。至此我们掌握了一个关键的"操作原型"——用一根空闲柱子做缓冲，就能把一个圆盘整体搬到目标柱上。

由 $f(2)$ 到 $f(3)$：子问题分解初现

$f(3)$ 的情况略复杂，但由于 $f(1)$、$f(2)$ 的解已知，可以把 A 顶部两个圆盘视为一个整体（这个整体恰好对应一个 $f(2)$ 子问题），从而把 $f(3)$ 化解为三步：

1. 令 B 为目标柱、C 为缓冲柱，把 $2$ 个圆盘从 A 移到 B（即求解 $f(2)$）；
2. 把 A 中剩余的最大圆盘直接移到 C（即求解 $f(1)$）；
3. 令 C 为目标柱、A 为缓冲柱，把 $2$ 个圆盘从 B 移到 C（再次求解 $f(2)$）。

从本质上说，$f(3)$ 被划分为两个 $f(2)$ 子问题与一个 $f(1)$ 子问题。依次解决这三个子问题，原问题即告解决——这正说明汉诺塔的子问题彼此独立、解可以合并，完全满足分治法的适用条件。

通用分治策略：$f(n) = f(n-1) + f(1) + f(n-1)$

将上述推演推广到一般情形，得到解决汉诺塔问题的通用分治策略：把原问题 $f(n)$ 划分为两个 $f(n-1)$ 和一个 $f(1)$，并按下述顺序求解：

1. 把 $n-1$ 个圆盘借助 C 从 A 移到 B（子问题 $f(n-1)$）；
2. 把剩余 $1$ 个圆盘从 A 直接移到 C（子问题 $f(1)$）；
3. 把 $n-1$ 个圆盘借助 A 从 B 移到 C（子问题 $f(n-1)$）。

两个 $f(n-1)$ 子问题又可以用完全相同的方式递归拆分，直到抵达最小子问题 $f(1)$。换句话说，求解过程中真正会变化的是三根柱子的角色（源柱/缓冲柱/目标柱）不断轮换，而"把 $i-1$ 个盘搬到缓冲柱、把最大的 1 个盘送到目标柱、再把 $i-1$ 个盘搬回目标柱"这一模式自始至终不变。

代码实现：dfs(i, src, buf, tar) 与 move() 的分工

《Hello 算法》在代码中把上述策略实现为递归函数 dfs(i, src, buf, tar)——将柱 src 顶部的 $i$ 个圆盘借助缓冲柱 buf 移到目标柱 tar。以 codes/python/chapter_divide_and_conquer/hanota.py 为例，完整实现如下：

def move(src: list[int], tar: list[int]):
    """移动一个圆盘"""
    # 从 src 顶部拿出一个圆盘
    pan = src.pop()
    # 将圆盘放入 tar 顶部
    tar.append(pan)

def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
    """求解汉诺塔问题 f(i)"""
    # 若 src 只剩下一个圆盘，则直接将其移到 tar
    if i == 1:
        move(src, tar)
        return
    # 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
    dfs(i - 1, src, tar, buf)
    # 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
    move(src, tar)
    # 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
    dfs(i - 1, buf, src, tar)

def solve_hanota(A: list[int], B: list[int], C: list[int]):
    """求解汉诺塔问题"""
    n = len(A)
    # 将 A 顶部 n 个圆盘借助 B 移到 C
    dfs(n, A, B, C)

逐行拆解代码的巧妙之处

这段代码虽然短小，却浓缩了整个分治思想：

• move(src, tar) 是原子操作：只负责"从源柱顶部弹出、压入目标柱顶部"这一单盘移动，确保每条规则都成立。
• i == 1 是递归出口：只剩一个圆盘时无需缓冲，直接 move(src, tar)，对应 $f(1)$。
• 角色轮换靠交换实参实现：子问题 $f(i-1)$ 中，tar 变成了"缓冲柱"、buf 变成"目标柱"，因此调用写作 dfs(i - 1, src, tar, buf)；第三个子问题则写作 dfs(i - 1, buf, src, tar)。递归到不同深度时，三根柱子的身份由调用参数动态决定，这正是分治"统一模式、不同参数"的体现。
• 入口函数 solve_hanota 屏蔽细节：它从 A 的大小读出 $n$，调用一次 dfs(n, A, B, C) 即完成"借助 B 从 A 移到 C"的整体目标。

用列表表示柱子：Python / Java / C++ 的通用手法

仓库中使用了一种巧妙的建模方式——用列表/向量表示柱子，列表尾部视为柱顶。盘面按 $[5,4,3,2,1]$ 初始化的含义是：5 在最底部、1 在最顶部，与"尾部即顶部"的约定一致。这样 src.pop()（Python）、src.back(); src.pop_back()（C++）或 src.remove(src.size() - 1)（Java）就能天然模拟"从顶部取盘"。

Java 版见 codes/java/chapter_divide_and_conquer/hanota.java：

/* 移动一个圆盘 */
static void move(List<Integer> src, List<Integer> tar) {
    Integer pan = src.remove(src.size() - 1); // 从 src 顶部拿出
    tar.add(pan);                             // 放入 tar 顶部
}

/* 求解汉诺塔问题 f(i) */
static void dfs(int i, List<Integer> src, List<Integer> buf, List<Integer> tar) {
    if (i == 1) { move(src, tar); return; }
    dfs(i - 1, src, tar, buf);   // 子问题 f(i-1)：借助 tar 从 src 移到 buf
    move(src, tar);              // 子问题 f(1)
    dfs(i - 1, buf, src, tar);   // 子问题 f(i-1)：借助 src 从 buf 移到 tar
}

C++ 版（codes/cpp/chapter_divide_and_conquer/hanota.cpp）与 Java 结构完全一致；而 C 语言因不支持动态容器，改用"数组 + 大小指针"的组合（srcSize、tarSize）维护栈顶位置，实现在 codes/c/chapter_divide_and_conquer/hanota.c。Go 版则借助标准库 container/list 双向链表模拟柱子（codes/go/chapter_divide_and_conquer/hanota.go）。仓库中共提供了 Python、Java、C++、C、C#、JS、TS、Go、Swift、Rust、Ruby、Kotlin、Dart、Zig 等语言的同构实现，核心递归逻辑均一致。

运行与验证

• Python 直接执行即可观察结果：初始化 A = [5,4,3,2,1]，调用 solve_hanota 后打印三根柱子的最终状态，可见 $A$、$B$ 变空、$C = [5,4,3,2,1]$，顺序保持完整。
• Go 语言提供了标准测试入口 codes/go/chapter_divide_and_conquer/hanota_test.go：TestHanota 构造 5 个圆盘后调用 solveHanota 并打印验证结果，可作为自动化回归验证的参考模板。

复杂度分析：$O(2^n)$ 时间与 $O(n)$ 空间

从递归结构上看，汉诺塔问题会形成一棵高度为 $n$ 的递归树，每个节点对应一个被开启的 dfs() 调用（即一个子问题）。

• 时间复杂度 $O(2^n)$：每个 $f(n)$ 展开为两个 $f(n-1)$ 和一个 $f(1)$。设 $T(n)$ 为移动次数，有递推式 $T(n) = 2T(n-1) + 1$ 且 $T(1)=1$，解得 $T(n) = 2^n - 1$。也就是说，n 个圆盘最少需要 $2^n - 1$ 次移动，这正对应递归树的 $2^n - 1$ 个节点，因此时间复杂度为指数级 $O(2^n)$。
• 空间复杂度 $O(n)$：递归深度等于递归树高度 $n$，沿途每一层调用栈上只需要常数空间保存参数，故空间复杂度为 $O(n)$。

由此可见，汉诺塔问题虽然结构清晰、代码优雅，但本质上是一个指数级代价的问题——这正是其传说能"耗光宇宙时间"的数学根源。

数学趣闻：$64$ 个圆盘与"世界末日"传说

汉诺塔问题源自古老的传说：古印度一座寺庙中，僧侣们拥有三根高大的钻石柱和 $64$ 个大小不一的黄金圆盘，他们不停地搬运圆盘，并相信当最后一片圆盘被正确放好之时，世界便将终结。

由上面的递推式可知，搬运 $64$ 个圆盘需要 $2^{64}-1 \approx 1.84 \times 10^{19}$ 次移动。即便僧侣们每秒钟移动一次，也需要约 $5850$ 亿年——这远超当前对宇宙年龄的估算（约 138 亿年）。因此，即使传说属实，我们也完全无需为世界末日担忧。

小结

汉诺塔问题向读者展示了分治法更一般的一面：

对比维度	归并排序 / 建树	汉诺塔
分解方式	均匀拆成两个 $n/2$ 子问题	拆成两个 $f(n-1)$ 与一个 $f(1)$
子问题独立性	独立	独立（可依次求解并合并）
递归出口	子数组/区间长度 1	$i = 1$
复杂度	$O(n \log n)$	$O(2^n)$ 时间、$O(n)$ 空间

其核心启示是：分治法并不要求"均分"，关键在于把大问题转化为结构相同、可独立求解、解可合并的小问题。读者可对照分治法总论中的判断准则，或查阅本章习题进行巩固，并亲自运行 codes/python/chapter_divide_and_conquer/hanota.py 等代码观察每一步移动，直观体会递归的"角色轮换"之美。