通过二进制计数解决汉诺塔

汉诺塔可以通过遵循二进制计数的节奏解决。在第一部分，讲解者与曾教授计算机科学的 Keith Schwarz 介绍谜题及其背后的递归结构；后续视频再探索谢尔宾斯基三角形。

谜题有三根柱子和大小不同的圆盘，最初按从大到小叠好。目标是将整塔移到另一根柱子：每次只能移动一个圆盘，也不能把较大的圆盘放在较小的圆盘上。

例子把最小的圆盘标为 0，然后依次编号为 1、2 等。第一步必须移动圆盘 0。之后圆盘 1 不能放在圆盘 0 上，所以只能移到剩下的柱子。

Schwarz 的发现是，二进制计数的模式决定了移动哪个圆盘。为了理解原因，先看一般位值计数中进位的节奏。

十进制中，我们依次使用 0 到 9，然后个位归零、十位进一。重复足够多次后，十位也会进位，百位增加。相同模式在更大尺度上继续出现。

二进制只使用 0 和 1。在 0 和 1 之后，下一个数写作 10：一个二加零个一。接着 11 表示三，再加一得到 100，即一个四。

二进制位值是 2 的幂：个位、二位、四位、八位等。进位发生得很频繁，因此重复结构尤其容易看见。

在每个尺度上，二进制计数都有相同形式：先数完一个较小范围，向下一位进位，再重复较小的模式。例如数到 1111，要先让最后三位数满，再向八位进位，然后让最后三位再数一遍。

从零开始用二进制计数。每次加一只改变最后一位时，将最小圆盘向右移动一根柱子；如果已在最右边，就绕回第一根柱子。固定方向会决定最终完成的塔落在哪根目标柱上；反转方向则选择另一根。

当进位到达二位时，移动圆盘 1。除了放有圆盘 0 的柱子，它只有一个合法去处。进位到四位时移动圆盘 2，进位到八位时移动圆盘 3，以此类推。

得到的移动顺序以 0、1、0、2、0、1、0、3 开始。这个规则令人惊讶：为什么每次进位时对应的大圆盘恰好可以移动？又为什么它能高效完成任务？

Schwarz 用递归视角解释：为了把一个大圆盘移到目标柱，必须先把所有较小圆盘叠到备用柱上。然后移动大圆盘一次，最后把小塔移到它上面。

较小的塔本身又是一个圆盘更少、规则相同的问题。每个圆盘都遵循同一模式：先移开上方圆盘，移动自己，再把小塔放回上面。

这一思路也证明了最优性。最大圆盘移动前，所有较小圆盘都必须移开；移动后，又必须把它们移到最大圆盘上。设 T(n) 为最少移动次数，则 T(n)=2T(n−1)+1，T(0)=0，因此 T(n)=2ⁿ−1。

二进制计数与这一递归过程相对应：完成较小的模式、向下一位进位，再完成一次较小模式。每一步移动的圆盘，对应加一时从 0 变为 1 的最高位。

两个圆盘的顺序是圆盘 0、圆盘 1、圆盘 0，与数到二进制 11 的进位模式相同。三个圆盘则先解两圆盘问题，再移动圆盘 2，再解一次两圆盘问题，对应更大尺度的二进制模式。

在每个尺度上，两者都有“子问题、一步操作、子问题”的结构。因此，观察变化的二进制位就能重构汉诺塔的递归算法。视频承诺在第二部分解释与谢尔宾斯基三角形的联系。