汉诺塔

汉诺塔（港台：河内塔）（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]