漢諾塔問題
[
又稱河內塔
]
是印度的一個古老的傳說。
據傳開天辟地之神勃拉瑪在一個廟里留下了三根金剛石的棒,第一根上面套著
64
個圓的金
片,最大的一個在底下,
其余一個比一個小,
依次疊上去,廟里的眾僧不倦地把它們一個個
地從這根棒搬到另一根棒上,
規定可利用中間的一根棒作為幫助,
但每次只能搬一個,
而且
大的不能放在小的上面。就是這看似簡單的問題,卻困擾了人們千年以上。
后來,這個傳說就演變為漢諾塔游戲,玩法如下
:
1.
有三根桿子
A,B,C
。
A
桿上有若干碟子
2.
每次移動一塊碟子
,
小的只能疊在大的上面
3.
把所有碟子從
A
桿全部移到
C
桿上
經過研究發現,三圓盤的漢諾塔問題很好破解,就是按照移動規則向一個方向移動金片:
如
3
階漢諾塔的移動:
A→C,A→B,C→B,A→C,B→A,B→C,A→C
但每當增加一階,
移動的次數卻會以倍數增加,
因此每當圓盤增加到一定數量時,
常人只能
望而卻步。
而我們程序員卻可以借助于計算機的運算性能,
輕而易舉地解決這一問題,
漢諾塔問題也作
為程序設計中的經典遞歸問題而存在下來。
但是,
實踐和理論往往卻有天壤之別,
我們雖然可以運算出漢諾塔的結果,
但是卻未必能動
手完成這一結果。
不信?我這里給出了一個簡單的漢諾塔實現,
有興趣的可以自己碼盤子看
看。
HannoiWindow
類的主要工功能是實現程序的窗口化。用的是
BordLayout
布局,采用
了菜單、按鈕、面板等組件,菜單主要包括選擇級別,盤子個數,設置大小等功能,它分別
調用了塔的名字
TowerName
(
A
,
B
,
C
)
、設置盤子的個數
SetAmountOfDisc
以及大小、
這個游戲可以選擇的級別
menuGrade
(初、中、高)
,按鈕的功能包括重新開始(
renew
)
和自動演示(
autoButton
)以及播放、暫停、演示、關閉等。
Disc
類的主要功能是建立一個類
disc
,然后通過調用盤子的設置數量、獲取數量以及
點的設置數量、獲取數量來實現這個程序的功能。
HannoiWindow
+Amountofdisc:int
+towerName:char[]
+
tower:Tower
+Hannoiwindow:
無類型
+actionPerformed(ActionEvent e):void
+main(String args[]):void
Disc
+Number:int
+Point:TowerPoint
Disc():
無類型
+SetNumber(int n):void
+getNumber():int
+SetPoint(TowerPoint):void
+getPoint():TowerPoint