减小
增大
默认

护眼
夜间
默认

汉诺塔问题

上一节
汉诺塔问题是一个经典的数学难题，由 3 个柱子和多个半径不等的圆盘构成，如下图所示：


图 1 汉诺塔问题

汉诺塔问题指的是：将一个柱子中的所有圆盘移动到另一个柱子，移动过程需遵守以下规则：
  • 每次只能移动一个圆盘，而且只能移动某个柱子上最顶部的圆盘；
  • 移动过程中，必须保证每个柱子上的大圆盘都位于小圆盘的下面。

如图 1 所示，第一个柱子上共有 3 个圆盘，下面的动画演示了汉诺塔问题的一种解决方案：


图 2 汉诺塔动画演示

可以看到，3 个圆盘需要移动 7 步，才能成功移动到另一个柱子上。

汉诺塔问题中，n 个圆盘至少需要 2n-1 次移动操作。

汉诺塔问题的解决思路

我们可以很轻易的想到移动 1~3 个圆盘的解决方案，圆盘个数越多，解决起来就越棘手。这种情况下，我们可以借助分治思想，将移动多个圆盘的大问题分割成多个移动少量圆盘的小问题。

为了便于讲清楚问题的解决过程，我们将 3 个柱子依次命名为起始柱、辅助柱及目标柱。起始柱指的是初始状态下所有圆盘所在的柱子，目标柱指的是最终放置所有圆盘的柱子，剩下的一个称为辅助柱。

首先，如果初始状态下的起始柱上仅有 1 个圆盘，我们可以很轻松地将圆盘从起始柱直接移到目标柱。如果初始状态下起始柱上有 2 个圆盘，则整个移动操作需执行如下几步：
  1. 将起始柱顶部较小的圆盘移动到辅助柱；
  2. 将起始柱上较大的圆盘移动到目标柱；
  3. 最后，将辅助柱上较小的圆盘移动到目标柱。

图 2 演示了以上 3 步操作的过程：


图 2 两个圆盘的移动过程

实际上，移动 2 个圆盘的过程也同样适用于移动更多的圆盘。对于初始状态下起始柱包含 2 个以上圆盘的情况（假设圆盘个数为 n），移动过程可以遵循以下步骤：
  1. 将起始柱上的 n-1 个圆盘移动到辅助柱；
  2. 将起始柱上最大的圆盘移动到目标柱；
  3. 将辅助柱中的 n-1个圆盘移动到目标柱。

对于移动 n-1 个圆盘的情况，仍可以遵循以上的移动过程。如此，我们就将移动 n 个圆盘的问题划分为移动 n-1 个圆盘的问题，此问题还可以进行更细致的划分。

汉诺塔问题的具体实现

下面以伪代码的方式给出了编程解决汉诺塔问题的整个过程：

hanoi(num , source , target , auxiliary):            // num 表示移动圆盘的数量，source、target、auxiliary 分别表示起始柱、目标柱和辅助柱
    if num == 1:                                                 // 如果圆盘数量仅有 1 个，则直接从起始柱移动到目标柱
        print(从 source 移动到 target)
    else:
        hanoi(num-1 , source , auxiliary , target) // 调用 hanoi 函数，将 num-1 个圆盘从起始柱移动到辅助柱上
        print(从 source 移动到 target)                  // 将起始柱上剩余的最后一个大圆盘移动到目标柱上
        hanoi(n-1 , auxiliary , target , source)      // 调用 hanoi 函数，将辅助柱上的 num-1 圆盘移动到目标柱上


下面为解决汉诺塔问题的 C 语言程序： 
#include <stdio.h>
void hanoi(int num, char source, char target,char auxiliary) {
    //统计移动次数
    static int i = 1;
    //如果圆盘数量仅有 1 个，则直接从起始柱移动到目标柱
    if (num == 1) {
        printf("第%d次:从 %c 移动至 %c\n", i, source, target);
        i++;
    }
    else {
        //递归调用 hanoi() 函数，将 num-1 个圆盘从起始柱移动到辅助柱上
        hanoi(num - 1, source, auxiliary, target);
        //将起始柱上剩余的最后一个大圆盘移动到目标柱上
        printf("第%d次:从 %c 移动至 %c\n", i, source, target);
        i++;
        //递归调用 hanoi() 函数，将辅助柱上的 num-1 圆盘移动到目标柱上
        hanoi(num - 1, auxiliary, target, source);
    }
}

int main()
{
    //以移动 3 个圆盘为例，起始柱、目标柱、辅助柱分别用 A、B、C 表示
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

如下为解决汉诺塔问题的 Java 程序： 
public class Demo {
    // 统计移动次数
    public static int i = 1;

    public static void hanoi(int num, char source, char target, char auxiliary) {
        // 如果圆盘数量仅有 1 个，则直接从起始柱移动到目标柱
        if (num == 1) {
            System.out.println("第" + i + "次:从" + source + "移动到" + target);
            i++;
        } else {
            // 递归调用 hanoi() 函数，将 num-1 个圆盘从起始柱移动到辅助柱上
            hanoi(num - 1, source, auxiliary, target);
            // 将起始柱上剩余的最后一个大圆盘移动到目标柱上
            System.out.println("第" + i + "次:从" + source + "移动到" + target);
            i++;
            // 递归调用 hanoi() 函数，将辅助柱上的 num-1 圆盘移动到目标柱上
            hanoi(num - 1, auxiliary, target, source);
        }
    }

    public static void main(String[] args) {
        // 以移动 3 个圆盘为例，起始柱、目标柱、辅助柱分别用 A、B、C 表示
        hanoi(3, 'A', 'B', 'C');
    }
}

如下为解决汉诺塔问题的 Python 程序： 
#记录移动次数
i = 1
def hanoi(num,source,target,auxiliary):
    global i
    if num==1:
        print("第%d次:从 %c 移动至 %c" % (i, source, target))
        i=i+1
    else:
        #递归调用 hanoi() 函数，将 num-1 个圆盘从起始柱移动到辅助柱上
        hanoi(num - 1, source, auxiliary, target)
        #将起始柱上剩余的最后一个大圆盘移动到目标柱上
        print("第%d次:从 %c 移动至 %c" % (i, source, target))
        i=i+1
        #递归调用 hanoi() 函数，将辅助柱上的 num-1 圆盘移动到目标柱上
        hanoi(num - 1, auxiliary, target, source)

#以移动 3 个圆盘为例，起始柱、目标柱、辅助柱分别用 A、B、C 表示
hanoi(3, 'A', 'B', 'C');

以上程序的输出结果均为：

第1次:从 A 移动至 B
第2次:从 A 移动至 C
第3次:从 B 移动至 C
第4次:从 A 移动至 B
第5次:从 C 移动至 A
第6次:从 C 移动至 B
第7次:从 A 移动至 B

上一节