算法：汉诺塔问题（Tower of Brahma puzzle）

一、算法背景

　　最早发明这个问题的人是法国数学家爱德华·卢卡斯。传说越南河内某间寺院有三根银棒(A, B, C)，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

A　　　　　　　　C　　　　　　　　B

二、汉诺塔算法

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

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

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

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

　　解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有 $N$ 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 ${displaystyle N-1}$ 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 ${displaystyle N-1}$ 块盘移到 C。如此递归地使用下去, 就可以求解。

 1     /**
 2      * Java递归函数解决河内塔之难题
 3      *
 4      * @param n 移动物体数量
 5      * @param fromRod 原先放的位置
 6      * @param toRod 要放去的位置
 7      * @param auxRod 中间留空方便转移的位置
 8      */
 9     private static void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
10         count++;
11         if (n == 1) {　　// 递归出口
12             System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
13             return;
14         }
15         towerOfHanoi(n-1, fromRod, auxRod, toRod);
16         System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);　　// 移动
17         towerOfHanoi(n-1, auxRod, toRod, fromRod);
18     }

　　设移动 n 个盘子的汉诺塔问题需要 towerOfHanoi(n) 次移动操作来完成。由展示移动过程算法可知 towerOfHanoi(n) 应是三部分之和。

　　(1) 将 n 个盘上面的 n-1 个盘子借助 C 桩从 A 桩移到 B 桩上，需 towerOfHanoi(n-1) 次移动；

　　(2) 然后将 A 桩上第 n 个盘子移到 C 桩上（1次）；

　　(3) 最后，将 B 桩上的 n-1 个盘子借助 A 桩移到 C 桩上，需 towerOfHanoi(n-1)次。

　　因而有递归关系： towerOfHanoi(n) = 2 * towerOfHanoi(n-1) + 1，初始条件(递归出口)： towerOfHanoi(1) = 1，即 1、3、7、15、31…… 移动次数 count = towerOfHanoi(n) = 2ⁿ -1 ，时间复杂度为 O(2ⁿ)。

本文源代码：

 1 package algorithm;
 2 
 3 /**
 4  * 汉诺塔问题（Tower of Brahma puzzle）
 5  *
 6  * 最早发明这个问题的人是法国数学家爱德华·卢卡斯。
 7  *
 8  * 传说越南河内某间寺院有三根银棒，上串 64 个金盘。
 9  * 寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。
10  * 这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。
11  * 但不知道是卢卡斯自创的这个传说，还是他受他人启发。
12  *
13  * 若传说属实，僧侣们需要 2^{64}-1 步才能完成这个任务；
14  * 若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。
15  *
16  * 这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。
17  * 寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。
18  * 另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。
19  */
20 public class TowerOfHanoi {
21     /* 移动次数 */
22     private static int count = 0;
23 
24     /**
25      * Java递归函数解决河内塔之难题
26      *
27      * @param n 移动物体数量
28      * @param fromRod 原先放的位置
29      * @param toRod 要放去的位置
30      * @param auxRod 中间留空方便转移的位置
31      */
32     private static void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
33         count++;
34         if (n == 1) {
35             System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
36             return;
37         }
38         towerOfHanoi(n-1, fromRod, auxRod, toRod);
39         System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
40         towerOfHanoi(n-1, auxRod, toRod, fromRod);
41     }
42 
43     public static void main(String[] args) {
44         int n = 4;
45         towerOfHanoi(n, 'A', 'C', 'B');
46         /**
47          * 可见移动次数是 (2^n-1), 其时间复杂度O(2^n)。
48          *
49          * 一天24h, 一小时60min, 一分钟60s, 一天有 24*60*60 = 86400(s), 一年平均365天来算，一年有 3153,6000 (s)
50          * 可见要几千亿年才能移动完, 这个算法用于移动大数量小空间的物体肯定是行不通的。
51          *
52          * 这个算法主要考验人的解决问题、逻辑思想, 以及计算推理的能力
53          */
54         System.out.println("移动次数：" + count);
55     }
56 }

View Code