汉诺塔

汉诺塔（港台：河內塔）（Tower of Hanoi）是根据一个传说形成的數學问题：

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

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

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

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

这里有汉诺塔在线页面，可以来体验汉诺塔，可以设置不同层数，也可以获取最优移动提示解。该在线游戏支持从任意初始状态获取最佳移动路径。

传说

最早發明這個問題的人是法國數學家愛德華·盧卡斯。

傳說越南河内某間寺院有三根銀棒，上串 64 个金盤。寺院裡的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完毕，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要 $2^{64}-1$ 步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位于越南的河內，所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。

解答

如取 N=64，最少需移动 2⁶⁴−1 次。即如果一秒钟能移动一块圆盘，仍需 5849 億年。目前按照宇宙大爆炸理論的推测，宇宙的年齡僅為 137 億年。

在真实玩具中，一般 N=8；最少需移动 255 次。如果 N=10，最少需移动 1023 次。如果N=15，最少需移动32767次；这就是说，如果一个人从 3 岁到 99 岁，每天移动一块圆盘，他最多仅能移动 15 块。如果 N=20，最少需移动 1048575 次，即超过了一百万次。

算法求解

解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有 $N$ 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 $N-1$ 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 $N-1$ 块盘移到 C。

如此递归地使用下去，就可以求解。

遞迴解

在 Java語言中：

public class HW {
	public static java.util.Scanner sc = new java.util.Scanner(System.in);
	public static void Towers(int n,char a,char b,char c){
		if(n==1){
			System.out.println("移動"+n+"從"+a+"到"+c);
		}
		else{
			Towers(n-1,a,c,b);
			System.out.println("移動"+n+"從"+a+"到"+c);
			Towers(n-1,b,a,c);
		}
	}

	public static void main(String[] args) {
		int n = sc.nextInt();
		Towers(n,'A','B','C');
	}
}

以 C++ 语言实现：

#include <iostream>
using namespace std;

void Towers(int n,char a,char b,char c){
	if(n==1){
		cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
	}
	else{
		Towers(n-1,a,c,b);
		cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
		Towers(n-1,b,a,c);
	}
}
int main(int argc, char *argv[]) {
	int n;
	cin>>n;
	Towers(n,'A','B','C');
	cout<< endl;
	
	
}

以 Python 语言实现：

def hanoi(n, a, b, c):
	if n == 1:
		print(a, '-->', c)
	else:
		hanoi(n - 1, a, c, b)
		hanoi(1    , a, b, c)
		hanoi(n - 1, b, a, c)
# 调用
if __name__ == '__main__':
	hanoi(5, 'A', 'B', 'C')

以 Erlang 语言求解：

-module(hanoi).
-export([hanoi/1]).
hanoi(N) when N>0 ->
	do_hanoi({N, 1, 3}).

do_hanoi({0, _, _}) ->
	done;
do_hanoi({1, From, To}) ->
	io:format("From ~p, To ~p~n", [From, To]);
do_hanoi({N, From, To}) ->
	do_hanoi({N-1, From, by(From, To)}),
	do_hanoi({1, From, To}),
	do_hanoi({N-1, by(From, To), To}).

by(From, To) ->
	[Result|_] = [1, 2, 3] -- [From, To],
	Result.

以 Haskell 语言实现：

hanoi :: Integer -> String -> String -> String -> [(String, String)]
hanoi 0 _ _ _ = []
hanoi 1 from _ to = [(from, to)]
hanoi x from buffer to = 
    hanoi (x-1) from to buffer ++ hanoi 1 from buffer to ++ hanoi (x-1) buffer from to

任意初始結構（arbitrary initial configuration）的解法

為了從任意初始結構中找尋最佳解（optimal solution），其演算法可以一般化（be generalized）如下：

以 Scheme 語言表示：

 ; Let conf be a list of the positions of the disks in order of increasing size.
 ; Let the pegs be identified by the numbers 0, 1 and 2.
 (define (hanoi conf t)
  (let ((c (list->vector conf)))
   (define (move h f t)
    (vector-set! c h t)
    (printf "move disk ~s from peg ~s to peg ~s~n" h f t))
   (define (third-peg f t) (- 3 f t))
   (define (hanoi h t)
    (if (> h 0)
     (let ((h (sub1 h)))
      (let ((f (vector-ref c h)))
       (if (not (= f t))
        (let ((r (third-peg f t)))
         (hanoi h r)
         (move h f t)))
       (hanoi h t)))))
   (hanoi (vector-length c) t)))

在 Java語言中：

    
public class Hanoi {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(hanoiFunc(7));
	}

	public static int hanoiFunc(int i) {
		int sum = 0;

		if (i == 1) {
			sum += i;
		}

		else {
			sum = 2 * hanoiFunc(i - 1) + 1;
		}

		return sum;
	}
}

在 C語言中：

int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */

void move(int d, int t) {
    /* move disk d to peg t */
    conf[d] = t;
}

void hanoi(int h, int t) {
    if (h > 0) {
        int f = conf[h-1];
        if (f != t) {
            int r = 3 - f - t ;
            hanoi(h-1, r);
            move(h-1, t);
        }
        hanoi(h-1, t);
    }
}

图像解释

可以用无向图来表示汉诺塔，在表示的时候会更加地直观和清晰，虽然说理解上有一点难度。

现在规定，每一个节点表示盘子的位置一种可能性，每一条边表示一种移动的方法。

注：这里不考虑在两个柱子之间的，没有意义的，来回移动的情况。

对于只有一个盘子的汉诺塔，可以表示为：

一个盘子的情况

对于有两个盘子的汉诺塔，可以表示为：

相互连接的三个三角形，组成了一个较大三角形的三个角。

每一个节点的第二个字母表示更大的盘子，且最初时没有被移动。

对于每一个顶端的小三角形，表示两个盘子的一种移动的方法：

两个盘子的汉诺塔

外围的三角形的每一个节点，表示在一个柱子上盘子的所有分布可能。

对于 h+1 个盘子，就可以"复制" h 个盘子时候的三角形图，然后拼成一个新的大三角形图，稍微改动一下，

这个大的三角形图就可以用来表示 h+1 个盘子时的情况了。

所以当有三个盘子时，图形为：

三个盘子的汉诺塔

a、b 和 c 表示三个柱子

按照从小到大的顺序，从左到右地列出的盘子的位置。

最外面的三角形的边，表示了盘子从一个柱子移动到另一个柱子最快的方式。最大的三角形可以沿着中线分成三个次小的三角形，就是上面由二级的汉诺塔组成三级的汉诺塔的逆向操作，次小三角形相互之间的连线，表示着最大的盘子的移动方式。

同理，在这次三角形的也可以沿其中线分割成为三个次次三角形，一样的，次次小三角形相互之间的连线，表示着次大的盘子的移动方式。继续下去，也就可以表示出一个汉诺塔的移动方式。

具有七个盘子的汉诺塔的图与七级的谢尔宾斯基三角形的联系

通常，对于具有 n 个盘子的图，有 $3^{n}$ 个节点；每个节点都有三条边连接着其他节点，但是在顶点的的节点只却只有有两条边连接着其他节点。所以说总是下都可以将最小的盘子移动到另外两个柱子中的一个，对于多数情况，是可以在两个柱子间移动一个盘子，除了所有的盘子都在一个柱子上。边角的节点表示着所有的盘子都在一个柱子的情况，即可以在 a， b 或 c 柱上堆满盘子，显然只要三种。对于 $n+1$ 个盘子的图，可以通过表示 $n$ 给盘子的图 "复制" 三份，组合在一起的。因此也就很方便地表示了每一层的汉诺塔移动方式，每一个次小的三角形表示次小的盘子的所有可能的移动方式和放置状态，次小的三角形之间的连接表示了大盘子的三种可能的移动方式。所以图形有 $3^{n}+1$ 个节点，基本都有三个与之相连接的边，而顶点只有两个。

在盘子数比较多的时候，汉诺塔的图像就会开始和分形图比较相似了。

如果使用最麻烦的移动方式，即不走重复的路(移动方式)，需要 $3^{64}-1$ 次移动，每秒移动一次，需要的时间超过 $10^{23}$ 年。

在不考虑重复使用路径的情况下，去除掉没有经过的边，就可以表示出当有三个盘子时的最长路径。

就是没有去做无意义 (多余的) 的，将一个盘子在两个柱子间疯狂来回移动的情况下，去除没有使用的移动方法，就可以得到当有三个盘子时的最麻烦的移动方式

三个盘子的汉诺塔 - 通路

顺便一提，这个最长的非重复路径，可以通过清除掉从 a 到 b 的路径得到。

也可以得出三个盘子的汉诺塔图的哈密顿回路：

三个盘子的汉诺塔的哈密顿回路

该图较为清楚地表达了：

对于任意的全部盘子在一根柱子的情况下，将所有盘子移动到另一个柱子的最短路径只有一个。
对于任意的两个盘子分布情况之间转换的时候，只有一个或者两个不同的最短路径。
对于任意的盘子分布情况，都有一个或者两个将所有盘子移动到任意一个柱子上的最长不相交路径。
对于任意的两个盘子分布情况之间转换的时候，只有一个或者两个不同的最长不相交路径。
设 $N_{h}$ 是将有 $h$ 个盘子的塔，将所有盘子从一个柱子移动到另一个柱子的非相交路径的数量(一开始盘子都在一个柱子上)。可以得出：
- $N_{1}=1$ N 1 = 2，
- $N_{h+1}=(N_{h})^{2}+(N_{h})^{3}$ 。

这里的 $N_{h}\in \{2,12,1872,6563711232,....\}$ ，详细在 A125295上。

多塔汉诺塔问题

在有 3 个柱子时，所需步数的公式较简单，但对于 4 个柱子以上時，情形複雜許多。Frame 及 Stewart 在 1941年時分別提出了基本上相同的一套演算法^[1]，Bousch 則在 2014年證明了Frame-Stewart演算法在 4 個柱子時就是最佳解^[2]，但此演算法在 5 個柱子以上是否是最佳解仍是未知。

Frame-Stewart 演算法本質上也是递归的，可簡單敘述如下：

令 $f(n,k)$ 为在有 $k$ 个柱子时，移动n个圆盘到另一柱子上需要的步数，则：

对于任何移动方法，必定会先将

m(1\leq m\leq n-1)

个圆盘移动到一个中间柱子上，再将第

n

到第

n-m

个圆盘通过剩下的

k-1

个柱子移到目标柱子上，最后将

m

个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为

2f(m,k)+f(n-m,k-1)

。

进行最优化，易得：

f(n,k)=\mathrm {min} _{m\in [1,n-1]}\;(2f(m,k)+f(n-m,k-1))

。

流行文化

2011年電影《猿人爭霸戰：猩凶革命》曾出現河內塔以測試猩猩的智商。其后续电影《猩球崛起2》中也有类似的场景。

參見

參考來源

^ Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268. doi:10.2307/2304268.
^ Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21: 895–912.

外部連結

[1] Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268. doi:10.2307/2304268.

[2] Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21: 895–912.

[1]

[2]