基于ＪＳＳＥ的漢諾塔游戲設計與實現

摘要：對漢諾塔游戲問題進行了研究，發現了對漢諾塔游戲用遞歸算法實現符合問題邏輯結構。設計了基于JSSE的遞歸算法實現了手動移盤和自動移盤的游戲功能。

關鍵詞：漢諾塔；盤子問題；游戲設計

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)08-10ppp-0c

1 引言

相傳在古印度的布拉瑪婆羅門圣廟的僧侶在進行一種被稱為漢諾塔的游戲，其裝置是一塊銅板，上面有三根桿（編號A、B、C），A桿上自下而上、由大到小按順序串上64個金盤。游戲的目標是把 A桿上的金盤全部移到C桿上，并仍原有順序疊好。條件是每次只能移動一個盤，并且在每次移動都不允許大盤移到小盤之上。僧侶們說游戲結束的時候就是世界末日。現要求利用遞歸調用技術把N個盤從A桿移到C桿的移動過程演示出來。

2 問題分析

這是一個著名的問題，幾乎所有的教材上都有這個問題。由于條件是一次只能移動一個盤，且不允許大盤放在小盤上面，所以64個盤的移動次數是：18，446，744，073，709，551，615 這是一個天文數字，若每一微秒可能計算(并不輸出)一次移動，那么也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔，但很難用計算機解決64層的漢諾塔。

分析問題，找出移動盤子的正確算法。

這個移動過程很復雜與煩瑣，但規律性卻很強。使用遞歸調用技術來解決這個移動過程，先得找到一個遞歸調用模型。想要得到漢諾塔問題的簡單解法，著眼點應該是移動A桿最底部的大盤，而不是其頂部的小盤。不考慮64個盤而考慮N個盤的一般情況。要想將A桿上的N個盤移至C桿，我們可以這樣設想：

（1）以C盤為臨時桿，從A桿將1至N-1號盤移至B桿。

（2）將A桿中剩下的第N號盤移至C桿。

（3）以A桿為臨時桿，從B桿將1至N-1號盤移至C桿。

我們看到，步驟2只需移動一次就可以完成；步驟1與3的操作則完全相同， 唯一區別僅在于各桿的作用有所不同。這樣，原問題被轉換為與原問題相同性質的、規模小一些的新問題。 這就是需要找的遞歸調用模型。

3 遞歸算法設計

根據以上分析，在三個柱子中選擇一個作為臨時桿，可得到基本遞歸算法如下：

public class TowersOfHanoi//實現遞歸算法的類

{

private int totalDisks;

public TowersOfHanoi(int disks)

{

totalDisks=disks;

}

public void solve()

{

moveTower (totalDisks，1，3，2);

}

privatevoid moveTower(int numDisks，int start，int end，int temp)

{

if(numDisks==1)

moveOneDisk(start，end);

else

{

moveTower(numDisks-1，start，temp，end);

moveOneDisk(start，end);

moveTower(numDisks-1，temp，end，start);

}

}

privatevoid moveOneDisk(int start，int end)

{

System.out.println(\"Move one disk from\"+start+\"to\"+end);

}

}

4 游戲界面設計

4.1 布局設計

在Java的GUI界面設計中，布局控制是通過為容器設置布局編輯器來實現的。java.awt包中共定義了五種布局編輯類，每個布局編輯類對應一種布局編輯策略，分別是FlowLayout、BorderLayout、CardLayout、GridLayout和GridBagLayout。當一個容器選定一種布局編輯策略時，它應該創建該策略對應的布局編輯類的對象，并將此對象設置為自己的布局編輯器。沒有設置布局編輯器的容器，其中的對象會互相覆蓋，影響使用，所以必須為每個容器設置一個合適的布局編輯器。

本游戲界面采用BorderLayout布局編輯器實現布局控制，它把容器內的空間簡單地劃分為東、西、南、北、中五個區域，每加入一個組件都應該指明把這個組件加在哪個區域中。

BorderLayout只能指定五個區域位置，如果容器中需要加入超過五個組件，就必須使用容器的嵌套或改用其他的布局策略。

4.2 GUI組件設計

4.2.1 容器設計

容器組件的主要作用是包容其他組件并按一定的方式組織排列它們，同一個容器中的所有部件通常總是同時被顯示和同時被隱藏的。從AWT組件體系結構中可以看出，所有的容器組件都是Container類的子類，而Container類又是Component類的子類。作為Container子類的容器可以分為三組：Panel和Applet一組的容器都是無邊框的；ScrollPane一組是可以自動處理滾動操作的容器；Windows、Frame、Dialog和FileDialog是一組大都含有邊框，可以移動、放大、縮小、關閉，功能較強的容器。

4.2.2 盤子組件設計

游戲界面中的盤子類繼承Button按鈕，按鈕一般都對應一種特定的功能或操作，當用戶鼠標點擊按鈕時，系統就執行這個預先定義好的操作。本游戲中有手動移盤的操作，故將盤子類設計為按鈕Button類的子類，以方便手工移動。另外為每個盤子設置唯一的編號以區別大小不同的盤子。最后為盤子類設置屬性上方有盤，以判斷每個盤子對象上面是否還有其他盤子。如果該屬性值為真，表示不能移動該盤子。

class Disk extends Button {

private static final long serialVersionUID = -6174681128406353175L;

int number;

boolean 上方有盤 = 1;

public Disk(int number， HannoiTower con) {

this.number = number;

setBackground(Color.blue);

addMouseMotionListener(con);

addMouseListener(con);

}

public boolean get上方有盤() {

return 上方有盤;

}

public void set上方有盤(boolean b) {

上方有盤 = b;

}

public int getNumber() {

return number;

}

}

4.2.3 塔節點設計

塔節點的功能是實現盤子在移動過程中的定位。故應為該類的對象設置橫縱坐標屬性。塔節點表示盤子放置的位置，還應該設置一個布爾屬性表示該節點現在有沒有盤子，只有當沒有盤子時才能放置。最后還要設置返回該屬性值的方法等。

class TowerPoint {

int x， y;

boolean 有盤子;

Disk 盤子 = 1;

HannoiTower con = 1;

public TowerPoint(int x， int y， boolean boo) {

this.x = x;

this.y = y;

有盤子 = boo;

}

public boolean 是否有盤子() {

return 有盤子;

}

public void set有盤子(boolean boo) {

有盤子 = boo;

}

public int getX() {

return x;

}

public int getY() {

return y;

}

public void 放置盤子(Disk 盤子， HannoiTower con) {

this.con = con;

con.setLayout(1);

this.盤子 = 盤子;

con.add(盤子);

int w = 盤子.getBounds().width;

int h = 盤子.getBounds().height;

盤子.setBounds(x - w / 2， y - h / 2， w， h);

有盤子 = true;

con.validate();

}

public Disk 獲取盤子() {

return 盤子;

}

}

4.3 事件處理機制

圖形用戶界面之所以能為廣大用戶所喜愛并最終成為事實上的標準，很重要的一點就在與它可以用更靈活、簡便的方式來接收用戶命令。用戶在圖形用戶界面中輸入命令是通過移動鼠標對特定圖形界面元素單擊、雙擊鼠標或擊鍵來實現的，為了能夠接受用戶命令，圖形用戶界面首先應該能夠識別這些操作并做出相應的響應。通常每一個鍵盤或鼠標操作會引發一個系統預先定義好的事件，用戶程序只須編制代碼定義每個特定事件發生時程序應作出何種響應即可。這些代碼會在它們對應的事件發生時由系統自動調用，這就是圖形用戶界面中事件和事件響應的基本原理。如下代碼是鼠標拖動事件的處理：

public void mouseDragged(MouseEvent e) {

Disk disk = 1;

if (e.getSource() instanceof Disk) {

disk = (Disk) e.getSource();

move = true;

e = SwingUtilities.convertMouseEvent(disk， e， this);

}

if (e.getSource() == this) {

if (move disk != 1) {

x = e.getX();

y = e.getY();

if (disk.get上方有盤() == 1)

disk.setLocation(x - disk.getWidth() / 2， y

- disk.getHeight() / 2);

}

}

}

5游戲運行演示

圖1 將1號盤子移到B柱

圖2 最終效果：將1號盤子移到C柱

5 結束語

一般的算法是很難解決這個問題的，而用遞歸算法只用了幾個語句就解決了這個難題。不過要說明的是，按照漢諾塔的移動原則，將N個盤從A桿移動到C 桿需要移動盤的次數是2的N次冪減1，那么64個盤移動次數就是18446744073709511615，近19億億次。這是一個天文數字，即使一臺功能很強的現代計算機來解漢諾塔問題，恐怕也需要很長的時間，因此要想得到結果，在運行程序時，輸入的N可不能太大。據說布拉瑪婆羅門圣廟的僧侶聲稱， 漢諾塔游科學家以能源角度推算，太陽系的壽命只不過150億年而已。看來僧侶們說的不假啊！

參考文獻：

[1]魯輝.JAVA程序設計[M].北京：地質出版社，2006.

[2]青野雅樹.基于JAVA的計算機圖形學[M].北京：科學出版社，2004.

[3]劉偉，朱詩兵.java2精要語言詳解與編程指南[M].北京：清華大學出版社，2006.

[4]陸遲編.Java語言程序設計[M].北京：電子工業出版社，2005.