本頁使用了標題或全文手工轉換

河內塔

維基百科,自由的百科全書
前往: 導覽搜尋
常見玩具版漢諾塔有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 from, char buffer, char to)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
 
    }
    else
    {
        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;
}
 
// 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年電影《猩球崛起》曾出現河內塔以測試猩猩智商。其後續電影《猩球崛起2》中也有類似的場景。