汉诺塔问题

汉诺塔（台港：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题^[1]https://zh.wikipedia.org/wiki/汉诺塔：

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

• 每次只能移动一个圆盘；
• 大盘不能叠在小盘上面。

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

求解

• 考虑最简单的情况，只有一个圆盘，此时直接将圆盘移动到 C 即可。
• 有两个圆盘时，首先将上面的移动到 B，然后将下面的移动到 C，在将 B 上的移动到 C
• 有3个圆盘时，可以设想如果最下面的那个不存在，那么问题就等于只有2个圆盘了，只不过此时不把这两个圆盘移动到C，而是借助C移动到B上，然后将A上的第三个圆盘移动到C，在借助A将B上的移动到C
• 因此，有 $n$ 个圆盘时，将问题分解为 $n-1$ 和 第 $n$ 个，首先借助 C 将 前 $n-1$ 个移动到B，第$n$个移动到C，在借助 A 将 B 的那 $n-1$ 个移动到 C
• 通过以上分析发现子问题需要做两次（借助C移动到B和借助A移动到C），加上一次 第 n 个移动到 C 的操作，因此存在递推关系 $T(n) = 2T(n-1) + 1$
• 以上递归关系可知，子问题需要的时间翻倍之后便是此问题需要的时间，那么复杂度为 $\ O(2^n)$

推导

已知 $T(n) = 2T(n-1) + 1$，那么可知

$$
\begin{align}
T(1) & = 2T(0) + 1 = 2^0 + 2^0 - 1\\
T(2) & = 2T(1) + 1 = 2^1 + 2^1 - 1\\
T(3) & = 2T(2) + 1 = 2^2 + 2^2 - 1 \\
…\\
T(n) & = 2T(n-1) + 1 = 2^{n-1} + 2^{n-1} - 1 = 2^n - 1\\
\end{align}
$$

因此

$$T(n) = 2^n - 1 = \ O(2^n)$$

代码