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

河内塔（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{array}{l}{T}_0=0\\ T_n=2T_{n-1}+1& (n>0)\end{array}$$

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

• 方法一（归纳法，induction）

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

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

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

• 方法二

递推公式两边加 1，则

$$\{\begin{array}{l}{T}_0+1=1\\ T_n+1=2T_{n-1}+2& (n>0)\end{array}$$

令 $U_n=T_n+1$，则

$$\{\begin{array}{l}{U}_0=1\\ U_n=2U_{n-1}& (n>0)\end{array}$$

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

$$T_n=2^n-1$$