数据结构：汉诺塔问题的递归求解和分析

递归方法求解该类问题，是一种简单的思维方法，通常比使用迭代方法更简单。但是，递归方法也有劣势。此处以典型的汉诺塔问题（Tower of Hanoi）为例给予说明。

汉诺塔是根据一个传说形成的数学问题，最早是由法国数学家爱德华·卢卡斯提出。

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

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

问：如何移动？最少要移动多少次？

下面链接是一个汉诺塔问题的交互操作程序，读者可以通过操作，尝试解决此问题。https://www.mathsisfun.com/games/towerofhanoi.html

汉诺塔问题，以及之前遇到过的阶乘、斐波那契数列等，都是分治思想的典型应用。

对于汉诺塔问题，解决方法如下，如图 5.1.1 所示。

假设 A 柱上最初的盘子总数为 $n$ 。

• 当 $n=1$ 时，只要将编号为 1 的圆盘从 A 直接移至 C 上即可。
• 否则，执行如下三步：
  1. 用 C 柱做过渡，将 A 柱上的 $(n-1)$ 个盘子移到 B 柱上；
  2. 将 A 柱上最后一个盘子直接移到 C 柱上；
  3. 用 A 柱做过渡，将 B 柱上的 $(n-1)$ 个盘子移到 C 柱上。

由上述求解过程可知，汉诺塔问题符合分治算法的递归求解要求。

【算法步骤】

1. 如果 $n=1$ ，则直接将编号为 1 的圆盘从 A 移到 C，递归结束。
2. 否则：
   • 递归，将 A 上编号为 1 至 $n-1$ 的圆盘移到 B，C 做辅助塔；
   • 直接将编号为 n 的圆盘从 A 移到 C；
   • 递归，将 B 上编号为 1 至 $n-1$ 的圆盘移到 C，A 做辅助塔。

【算法描述】

//定义搬动操作函数 move(A, n, C) ，将编号为 n 的圆盘
// 从 A 移到 C。
//用全局变量 m 对搬动次数计数
int m = 0;
void move(char A, int n, char C){
    cout << ++m <<"," << n << "," << A << "," << C << endl;
}

void Hanoi(int n, char A, char B, char C){
    //将 A 上的 n 个圆盘移到 C 上，B 做辅助塔
    if (n == 1) move(A, 1, C); //将编号为 1 的圆盘从 A 移到 C
    else {
        Hanoi(n-1, A, C, B); //将 A 上不编号为 1 至 n-1 的圆盘移到 B ，C 做辅助塔
        move(A, n, C);  //编号为 n 的圆盘从 A 移到 C
        Hanoi(n-1, B, A, C); //将 B 上编号为 1 至 n-1 的圆盘移到 C，A 做辅助塔
    }
}

【算法分析】

假设圆盘数量为 $n$ 时，移动圆盘的时间复杂度为 $T(n)$ ；圆盘数量为 $(n-1)$ 时时间复杂度 $T(n-1)$ 。根据算法，要将 $n-1$ 个圆盘从 A 移到 B（借助 C），然后将这些圆盘从 B 移到 C（借助 A）。再加上将编号为 n 的圆盘从 A 移到 C 所花费的常数时间（用 $c$ 表示）则得到递推公式：
$$T(n)=2T(n-1)+c$$
根据递推公式，有：
$$\begin{array}{rl}T(n)& =2T(n-1)+c=2[2T(n-2)+c]+c\\ & =2^{2}T(n-2)+[2+1]c=2^2[2T(n-3)+c]+[2+1]c\\ & =2^{3}T(n-3)+[2^2+2+1]c\\ & ⋮\\ & =2^{n-1}T(1)+[2^{n-2}+\cdots +2^0]c\end{array}$$
显然 $T(1)=c$

上述汉诺塔问题算法的时间复杂度是 $O(2^n)$ ，即指数阶的时间复杂度。

在第 2 章（因为本文是我编写的《数据结构》考研复习讲义中的节选，所以，读者在阅读的时候，如果遇到类似的表述，勿要深究）已经研究过这种指数阶时间复杂度，在一般情况下， 无法用于解决实际问题，不是一个有效的算法。

对于汉诺塔问题的时间复杂度分析，也可以通过计算移动盘子的次数得到，借用前面给出的交互演示程序和算法，可知：

因此时间复杂度为 $O(2^n)$ 。