本页使用了标题或全文手工转换

汉诺塔

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

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

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

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

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

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

传说[编辑]

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

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

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

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

解答[编辑]

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

每次移动多于一块盘时,则再次使用上述算法来移动。

遞歸解[编辑]

C++ 语言实现:

using namespace std;
#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 0) return;
    hannoi (n-1, from, to, buffer);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hannoi (n-1, buffer, from, to);
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

Python 语言实现:

def hanoi(n, _from='A', buffer='B', to='C'): 
    if n == 0: return
    hanoi(n-1, _from, to, buffer)
    print('move', _from, '-->', to)
    hanoi(n-1, buffer, _from, to)

print(hanoi(5))


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)))

在 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个柱子以上時,情形複雜許多。Frame及Stewart在1941年時分別提出了基本上相同的一套演算法[1],Bousch則在2014年證明了Frame-Stewart演算法在4個柱子時就是最佳解[2],但此演算法在5個柱子以上是否是最佳解仍是未知。

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

  • 为在有k个柱子时,移动n个圆盘到另一柱子上需要的步数,则:
对于任何移动方法,必定会先将个圆盘移动到一个中间柱子上,再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上,最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为
进行最优化,易得:

流行文化[编辑]

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

參見[编辑]

參考來源[编辑]

  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. 

外部連結[编辑]