汉诺塔

维基百科,自由的百科全书
跳转至: 导航搜索
常见玩具版汉诺塔有8个圆盘
3个圆盘的汉诺塔的移动
4个圆盘的汉诺塔的移动

汉诺塔(港台:河內塔)是根据一个传说形成的數學问题:

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

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

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

问:如何移?最少要移动多少次?

解答[编辑]

如取N=64,最少需移动264-1次。即如果一秒钟能移动一块圆盘,仍将需5849.42亿年。目前按照宇宙大爆炸理论的推测,宇宙年龄仅为137亿年。

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

传说[编辑]

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

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

若傳說屬實,僧侶們需要264 − 1步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要5849億年才能完成。整個宇宙現在也不過137億年。

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

佛教中確實有「浮屠」()這種建築;有些浮屠亦遵守上述規則而建。「河內塔」一名可能是由中南半島在殖民時期傳入歐洲的。

解法[编辑]

許多的河內塔玩具都有 8 個碟子(disks)。在初學者看起來似乎不太可能有解,然而其演算法以程式語言來說如下:

遞歸解[编辑]

C++ 语言实现:

/*
 * Project     : hannoi
 * File        : main.cpp
 * Author      : iCoding
 *
 * Date & Time : Sat Oct 06 21:01:55 2012 
 *
 */
using namespace std;
#include <iostream>
#include <cstdio>
 
void hannoi (int n, char A, char B, char C)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
 
    }
    else
    {
        hannoi (n-1, A, C, B);
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
        hannoi (n-1, B, A, C);
    }
}
 
int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}
 
// end 
// iCoding@CodeLab
//

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.

任意初始結構(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)))

在 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);
    }
}

在PASCAL語言中:

procedure Hanoi(n: integer; from, to, by: char);
Begin
    if (n=1) then
        writeln('Move the plate ',n,' from ', from, ' to ', to)
    else begin
        Hanoi(n-1, from, by, to);
        Writeln('Move the plate ',n,' from ', from, ' to ', to);
        Hanoi(n-1, by, to, from);
    end;
End;

非遞歸解[编辑]

二元解[编辑]

多塔汉诺塔问题[编辑]

  • 在有3个柱子时,所需步数的公式较简单,但对于4个以上柱子的汉诺塔尚未得到通用公式,但有一递归公式(未得到证明,但目前为止没有找到反例):
  • f(n,k)为在有k个柱子时,移动n个圆盘到另一柱子上需要的步数,则:
对于任何移动方法,必定会先将m(1\le m\le 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年電影《猿人爭霸戰:猩凶革命》曾出現河內塔以測試猩猩智商