主題:資料結構～河內塔(Tower of Hanoi) 作者:李信宏(Delphi K.Top討論區站長) 日期:2002/08/31    [何謂河內塔] 這是唸過資訊系的學生必學的課程,故事的來源我引自九章出版社提供的資料如下: 1883年，一位法國的數學家 Edouard Lucas 教授在歐洲的一份雜誌上介紹了一個相當吸引人的難題──迷人的智力遊戲。這個遊戲名為河內塔(Tower of Hanoi)，它源自古印度神廟中的一段故事(也有一說是 Lucas 教授為增加此遊戲之神秘色彩而捏造的)。傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木釘的木板，在其中的一根木釘上，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片的金屬片移至三根木釘中的其中一根上。規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的金屬片都是直徑較小的被放在上層。直到有一天，僧侶們能將64片的金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。    [河內塔規則] 有A/B/C三個放置盤子的位置,一開始所有的盤子依大小堆疊在A位置上,當所有盤子全部被搬至C位置上,遊戲就結束,但是需遵守下面規則: 1.一次只能移動一個盤子。 2.大盤子永遠不能放在小盤子的上面。 3.這一疊盤子可以藉由另外一個外加的暫時位置從某個位置移到另外一個位置。    [河內塔搬動示範]

1                1
2  ->21 -> 12->  2
ABC  ABC  ABC  ABC

(圖片來源:出自教育部教材資源中心) [河內塔解法] 當任意N個盤子需搬移時，我們可以歸納出一套規則。 1.先將1到N-1號盤子從A經由C搬至B 2.再將最大的N號盤,由A搬至C 3.最後將1到N-1號盤子從B經由A搬至C 這就是遞迴法中將問題逐次縮小化的原則. [河內塔Delphi程式寫法] 解法有了,程式就很簡單了:

unit Unit1;    interface    uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;    type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;    var
  Form1: TForm1;    implementation    {$R *.DFM}
//河內塔的搬移遞迴程式
//將N個盤子從A經由B搬到C
procedure Move(n:integer;a,b,c:char);
begin
   if n>0 then // 結束遞迴的條件
   begin
      // 1.先將1到N-1號盤子從A經由C搬至B
      move(n-1,a,c,b); 
      // 2.再將最大的N號盤,由A搬至C
      form1.memo1.lines.add('move #' inttostr(n) ' ' a '->' c);
      // 3.最後將1到N-1號盤子從B經由A搬至C
      move(n-1,b,a,c);
   end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
  move(6,'A','B','C');
end;    end.

下次介紹遞迴轉非遞迴 ～～～Delphi K.Top討論區站長～～～

------
～～～Delphi K.Top討論區站長～～～

轉貼 http://go.to/tyy The Tower of Hanoi ( 2000.1.7 ) tyy 相信學過程式語言的朋友都知道，在學到遞迴程式這個章節時，老師最喜歡出的作業就是"河內塔"。網路上更是常常見到有人問這個程式要怎麼寫。 河內塔是啥東東我就懶得說了，反正我突然心血來潮，花了一個下午的時間，用BCB4.0寫了這個程式。其實這個程式真的很簡短，如果是用DOS文字模式來寫的話，程式碼幾行就搞定了。不過我寫的是視窗版的，主體部分如同以往，就那幾行就搞定了。但為了用圖形表達出移動Disk的畫面，反而寫了一堆有的沒有的程式碼。 按這裡下載執行檔和原始程式碼(Zip壓縮檔，232KB) http://home.kimo.com.tw/tyynote/hanoi.zip 發表人 - jackkcg 於 2002/09/07 00:03:45

------
**********************************************************
哈哈&兵燹
最會的2大絕招 這個不會與那個也不會 哈哈哈 粉好

Delphi K.Top的K.Top分兩個字解釋Top代表尖端的意思,希望本討論區能提供Delphi的尖端新知
K.表Knowlege 知識,就是本站的標語:Open our mind

(河內塔程式流程圖)     ---------------- 局局棋盤步步新， 變化無常平常待。 人生相處平常心， 無憂無慮心事成。 ----------------

mm....對不起,我今年修演算法,想知道演算法的答案是 1.就是一個程式 or 2.只是程式的描述 如給是2.不知高手可否提供演算法要如何寫Honi of Tower.謝謝先     發表人 -

引言: mm....對不起,我今年修演算法,想知道演算法的答案是 1.就是一個程式 or 2.只是程式的描述 如給是2.不知高手可否提供演算法要如何寫Honi of Tower.謝謝先

不是就這個嗎? [河內塔解法] 當任意N個盤子需搬移時，我們可以歸納出一套規則。 1.先將1到N-1號盤子從A經由C搬至B 2.再將最大的N號盤,由A搬至C 3.最後將1到N-1號盤子從B經由A搬至C ～～～Delphi K.Top討論區站長～～～

引言: mm....對不起,我今年修演算法,想知道演算法的答案是 1.就是一個程式 or 2.只是程式的描述 如給是2.不知高手可否提供演算法要如何寫Honi of Tower.謝謝先 發表人 - >< face="Verdana, Arial, Helvetica"> 演算法 資料結構=程式 當你要處理一個問題及一堆資料時,你必需決定資料以何種結構來建立,以化簡你的演算法,再依據演算法來寫成程式~~~ 簡單講,演算法只是處理資料的方法,目前已經有很多註名各式演算公式,了解並熟悉愈多的演算法,對你遇到大量資料時選用何種演算法來處理資料的效率有很大且明顯的直接關係,演算法更簡單講就是一種像數學一樣的東西,在理論基礎上教你如何處理這類或那類型的資料能獲得較快且正確的演算公式~~目前教科書大都以c架構語言在相關科書表示給讀書了解其實際程式運作的呈現方法~~其實若你能真正理解演算方法,用那種語言都一樣能在其環境中表示出來的~~只不過要先花一點點時間查查可能用到的函式及語言表示結構方式....再用該語言表達式寫出來囉,原理若能懂,各語言函式暫時等到真的想做某程式員時再來背熟某程式語言表逹式也不遲~~~ <凡走過必留跡,孔明傳是也>