求解河内塔移动步数的计算公式

河内塔（The Tower of Hanoi）问题介绍

河内塔问题，初始状态有 A、B、C 三根柱子，在 A 柱上从上到下重叠着从小到大的若干圆盘（看起来像塔一样）。

操作目标：将圆盘从 A 柱移到 C 柱，B 柱作为过渡。

移动规则：每次一步只能移动最上面的一个圆盘，只能将小圆盘放在大圆盘上。

令 $T_{n-1}$ 为将 $n-1$ 个圆盘从一柱移至另一柱的（最少）步数。则含 $n$ 个圆盘的河内塔移动完成可分解为三个步骤：

1. 将 $n-1$ 个圆盘从 A 柱移至 B 柱，需 $T_{n-1}$ 步；
2. 将最大的圆盘从 A 柱移至 C 柱，需 1 步；
3. 将 $n-1$ 个圆盘从 B 柱移至 C 柱，需 $T_{n-1}$ 步。

故完成 $n$ 个圆盘的河内塔需要步数

$$T_n = 2T_{n-1} + 1$$

即有递推公式

$$\begin{cases} T_0 = 0 \\[2ex] T_n = 2T_{n-1} + 1 & ( n > 0 ) \end{cases}$$

通过递推公式可以求得通项公式。

• 方法一（归纳法，induction）

根据递推公式计算出前几项值，观察可推测通项公式为 $T_n = 2^n - 1$。

归纳法证明关键步骤如下：

$$T_n = 2T_{n-1} + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 1$$

• 方法二

递推公式两边加 1，则

$$\begin{cases} T_0 + 1 = 1 \\[2ex] T_n + 1 = 2T_{n-1} + 2 & ( n > 0 ) \end{cases}$$

令 $U_n = T_n + 1$，则

$$\begin{cases} U_0 = 1 \\[2ex] U_n = 2U_{n-1} & ( n > 0 ) \end{cases}$$

显然 $U_n$ 的通项公式为 $U_n = 2^n$，则

$$T_n = 2^n - 1$$