以迭代解决汉诺塔问题的原理

, ,

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

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

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

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

汉诺塔是经典的数学问题，“如何移”的问题也是迭代教学的必考问题。但是以迭代解决其的原理多少有点糊里糊涂。

1
2
3
4
5
6
7
        _                 _                _
       | |               | |              | |
      _| |_              | |              | |
    _|_ _ _|_            | |              | |
  _|_ _ _ _ _|_          | |              | |
_|_____________|_________| |______________| |_______
      柱  A             柱  B             柱  C

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Tower of Hanoi 汉诺塔

# include <stdio.h>

void ToH(int len, char A, char B, char C){
    // 三根柱子分别标为 A, B, C
    if(len == 1) printf("[%d] Moved: %c -> %c\n", len, A, C);
    else{
        ToH(len - 1, A, C, B);
        printf("[%d] Moved: %c -> %c\n", len, A, C);
        ToH(len - 1, B, A, C);
    }
}
int main(void){
    char A = 'A', B = 'B', C = 'C';
    ToH(3, A, B, C);
    return 0;
}

迭代

函数迭代的基本思想就是将大问题逐步简化为易于解决的小问题，再从小问题一步一步逆推出整个问题的答案。比如下面阶乘的示例就是将数值一步一步缩小，直至变成易求出阶乘的 1 这个数：

1
2
3
4
long factorial(int val){
  if (val == 1) return 1;
  else return (factorial(val-1)*val);
}

整体思想

因此，汉诺塔的题解也不应该过度关注每一步的走法，而应该从整体来看，将问题简化成两块圆盘（未在 C 柱上的最大圆盘，其余所有更小圆盘结成的组合体）的问题（其中，目标柱指前文字符画中的的柱 C，而在首次循环之前源柱代表柱 A，柱 B 是中转柱）：

1
2
3
4
5
6
7
graph TB
	A1[循环开始] -->A2[源柱上是否只有一个圆盘？]
	A2 --> |是|A3[将此圆盘移动至目标柱] --> A5[交换源柱和中转柱]
	A2 --> |否|A4[除最大的圆盘之外，将其他所有圆盘移至中转柱]
	A4--> B1[循环开始] -->B2[源柱上是否只有一个圆盘？]
	B2 --> |是|B3[将此圆盘移动至目标柱] --> B5[交换源柱和中转柱]
	B2 --> |否|B4[除最大的圆盘之外，将其他所有圆盘移至中转柱] --> ......

由此循环，不断将最大的圆盘放到目标柱上，直到源柱只剩一个圆盘。

而问题中，只有最后只剩一个圆盘没有被放上目标柱时状况是可预见、可计算的：“将此圆盘移动至目标柱”。因此就要以这一步为基推出之后的结果。

迭代体

因而，迭代体中 else 块的首个语句 ToH(len - 1, A, C, B); 的意义即是“将 A 柱（源柱）上所有的块都放入 B，只留最大的一块”[1]；第二句 printf("[%d] Moved: %c -> %c\n",len , A, C); 将最大的一块放到了 C 柱上；第三句 ToH(len - 1, B, A, C); 即是交换了源柱和中转柱的指向的实际柱（地址）并继续循环。

变量循环到最小值 1 时，出现了稳定结果，整个函数借此也可以完成迭代。

  1. 1.这一语句能够成立的前提就是“小圆盘可以放在大圆盘上”。由于目标柱最上的圆盘总是比其他两柱上的所有圆盘大，所以可以将其用作中转。 ↩