漢諾塔問題[又稱河內(nèi)塔]是印度的一個(gè)古老的傳說。
據(jù)傳開天辟地之神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。就是這看似簡(jiǎn)單的問題，卻困擾了人們千年以上。
后來，這個(gè)傳說就演變?yōu)闈h諾塔游戲，玩法如下:
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動(dòng)一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
經(jīng)過研究發(fā)現(xiàn)，三圓盤的漢諾塔問題很好破解，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片：
如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C
但每當(dāng)增加一階，移動(dòng)的次數(shù)卻會(huì)以倍數(shù)增加，因此每當(dāng)圓盤增加到一定數(shù)量時(shí)，常人只能望而卻步。
而我們程序員卻可以借助于計(jì)算機(jī)的運(yùn)算性能，輕而易舉地解決這一問題，漢諾塔問題也作為程序設(shè)計(jì)中的經(jīng)典遞歸問題而存在下來。
但是，實(shí)踐和理論往往卻有天壤之別，我們雖然可以運(yùn)算出漢諾塔的結(jié)果，但是卻未必能動(dòng)手完成這一結(jié)果。不信？我這里給出了一個(gè)簡(jiǎn)單的漢諾塔實(shí)現(xiàn)，有興趣的可以自己碼盤子看看。
package org.loon.test;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Menu;
import java.awt.MenuBar;
import java.awt.MenuItem;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
/**
* <p>
* Title: LoonFramework
* </p>
* <p>
* Description:java漢諾塔測(cè)試
* </p>
* <p>
* Copyright: Copyright (c) 2007
* </p>
* <p>
* Company: LoonFramework
* </p>
*
* @author chenpeng
* @email：ceponline@yahoo.com.cn
* @version 0.1
*/
public class Hanio extends Frame {
/**
*
*/
private static final long serialVersionUID = 1L;
private HanioDraw _hanioDraw;
public static void main(String args[]) {
new Hanio("java漢諾塔實(shí)現(xiàn)測(cè)試", 350, 300);
}
public Hanio(String string, int width, int height) {
super(string);
_hanioDraw = new HanioDraw();
setResizable(false);// 設(shè)為用戶不可改變窗體大小
setSize(width, height);// 設(shè)置窗口大小
setBackground(Color.WHITE);// 背景顏色設(shè)置為白色
// 菜單
MenuBar myMenu = new MenuBar();
Menu sMenu = new Menu("選擇數(shù)量");
MenuItem[] mItems = new MenuItem[6];
for (int i = 3; i <= 8; i++) {
mItems[i - 3] = new MenuItem(String.valueOf(i));
mItems[i - 3].addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
_hanioDraw.init(Integer.parseInt(((MenuItem) e.getSource())
.getLabel().toString()));
repaint();
}
});
sMenu.add(mItems[i - 3]);
}
myMenu.add(sMenu);
setMenuBar(myMenu);
setLayout(null);
// 加入窗體監(jiān)聽
addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
// 加入鼠標(biāo)監(jiān)聽
addMouseListener(new MouseAdapter() {
public void mouseClicked(MouseEvent e) {
Hanio hanio = (Hanio) e.getSource();
Dimension frSize = hanio.getSize();
int x = e.getX();
int w = frSize.width / 3;
if (x < w) {
hanio.getHanioDraw().click(0);
} else if (x < (2 * w)) {
hanio.getHanioDraw().click(1);
} else {
hanio.getHanioDraw().click(2);
}
hanio.repaint();
}
});
// 窗體居中
setLocationRelativeTo(null);
// 顯示窗口
setVisible(true);
}
public void paint(Graphics g) {
final int OBJECT_H = 15;// 對(duì)象高
final int OBJECT_W = 10;// 對(duì)象寬
final int OBJECT_D = 90;// 對(duì)象間距
final int OBJECT_S = 60;// 起始位置
// 繪制圖像
int n;
for (n = 0; n < 8; n++) {
if (_hanioDraw.getBlock(n, 0) != 0) {
g.drawRect(OBJECT_S, 200 - n * OBJECT_H, OBJECT_W
* _hanioDraw.getBlock(n, 0), OBJECT_H);
}
}
for (n = 0; n < 8; n++) {
if (_hanioDraw.getBlock(n, 1) != 0) {
g.drawRect(OBJECT_D + OBJECT_S, 200 - n * OBJECT_H, OBJECT_W
* _hanioDraw.getBlock(n, 1), OBJECT_H);
}
}
for (n = 0; n < 8; n++) {
if (_hanioDraw.getBlock(n, 2) != 0) {
g.drawRect(2 * OBJECT_D + OBJECT_S, 200 - n * OBJECT_H,
OBJECT_W * _hanioDraw.getBlock(n, 2), OBJECT_H);
}
}
if (_hanioDraw.getTop() != 0) {
g.drawRect(60, 60, OBJECT_W * _hanioDraw.getTop(), OBJECT_H);
}
if (_hanioDraw.goFull()) {
g.drawString("完成", 100, 100);
}
}
public HanioDraw getHanioDraw() {
return _hanioDraw;
}
public void setHanioDraw(HanioDraw hd) {
this._hanioDraw = hd;
}
class HanioDraw {
private int _top;// 拿起的方塊
private int _size;// 總數(shù)
private int[][] _room;// 用以存儲(chǔ)位置
private int[] _cache;// 緩存單個(gè)對(duì)象
public HanioDraw() {
_room = new int[8][3];
_cache = new int[3];
// 默認(rèn)初始值
init(3);
}
/**
* 開始處理
*
* @param x
*/
public void init(int x) {
_size = x - 1;
for (int i = 0; i <= 2; i++) {
for (int j = 0; j < 8; j++) {
_room[j][i] = 0;
}
_cache[i] = -1;
}
for (int i = 0; i < x; ++i) {
_room[i][0] = x - i;
}
_cache[0] = x - 1;
_top = 0;
}
/**
* 拿起目標(biāo)對(duì)象
*
* @param x
* @return
*/
boolean take(int x) {
if (_cache[x] == -1)
return false;
_top = _room[_cache[x]][x];
_room[_cache[x]][x] = 0;
_cache[x]--;
return true;
}
/**
* 拖動(dòng)目標(biāo)對(duì)象
*
* @param x
* @return
*/
boolean drop(int x) {
if (_cache[x] != -1) {
if (_top > _room[_cache[x]][x])
return false;
}
_cache[x]++;
_room[_cache[x]][x] = _top;
_top = 0;
return true;
}
/**
* 判定事件是否完成
*
* @return
*/
public boolean goFull() {
if (_cache[1] == _size) {
return true;
}
if (_cache[2] == _size) {
return true;
}
return false;
}
/**
* 點(diǎn)擊事件
*
* @param x
* @return
*/
public boolean click(int x) {
if (goFull()) {
return false;
}
if (_top == 0) {
take(x);
} else {
drop(x);
}
return true;
}
public int getTop() {
return _top;
}
public int getBlock(int x, int group) {
return _room[x][group];
}
}
}
運(yùn)行圖如下：
據(jù)傳開天辟地之神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。就是這看似簡(jiǎn)單的問題，卻困擾了人們千年以上。
后來，這個(gè)傳說就演變?yōu)闈h諾塔游戲，玩法如下:
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動(dòng)一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
經(jīng)過研究發(fā)現(xiàn)，三圓盤的漢諾塔問題很好破解，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片：
如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C
但每當(dāng)增加一階，移動(dòng)的次數(shù)卻會(huì)以倍數(shù)增加，因此每當(dāng)圓盤增加到一定數(shù)量時(shí)，常人只能望而卻步。
而我們程序員卻可以借助于計(jì)算機(jī)的運(yùn)算性能，輕而易舉地解決這一問題，漢諾塔問題也作為程序設(shè)計(jì)中的經(jīng)典遞歸問題而存在下來。
但是，實(shí)踐和理論往往卻有天壤之別，我們雖然可以運(yùn)算出漢諾塔的結(jié)果，但是卻未必能動(dòng)手完成這一結(jié)果。不信？我這里給出了一個(gè)簡(jiǎn)單的漢諾塔實(shí)現(xiàn)，有興趣的可以自己碼盤子看看。
package org.loon.test;import java.awt.Color;import java.awt.Dimension;import java.awt.Frame;import java.awt.Graphics;import java.awt.Menu;import java.awt.MenuBar;import java.awt.MenuItem;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.MouseAdapter;import java.awt.event.MouseEvent;import java.awt.event.WindowAdapter;import java.awt.event.WindowEvent;/**
* <p> * Title: LoonFramework * </p> * <p> * Description:java漢諾塔測(cè)試 * </p> * <p> * Copyright: Copyright (c) 2007 * </p> * <p> * Company: LoonFramework * </p> * * @author chenpeng * @email：ceponline@yahoo.com.cn * @version 0.1 */public class Hanio extends Frame { /**
* */ private static final long serialVersionUID = 1L; private HanioDraw _hanioDraw; public static void main(String args[]) { new Hanio("java漢諾塔實(shí)現(xiàn)測(cè)試", 350, 300); } public Hanio(String string, int width, int height) { super(string); _hanioDraw = new HanioDraw(); setResizable(false);// 設(shè)為用戶不可改變窗體大小 setSize(width, height);// 設(shè)置窗口大小 setBackground(Color.WHITE);// 背景顏色設(shè)置為白色 // 菜單 MenuBar myMenu = new MenuBar(); Menu sMenu = new Menu("選擇數(shù)量"); MenuItem[] mItems = new MenuItem[6]; for (int i = 3; i <= 8; i++) { mItems[i - 3] = new MenuItem(String.valueOf(i)); mItems[i - 3].addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { _hanioDraw.init(Integer.parseInt(((MenuItem) e.getSource()) .getLabel().toString())); repaint(); } }); sMenu.add(mItems[i - 3]); } myMenu.add(sMenu); setMenuBar(myMenu); setLayout(null); // 加入窗體監(jiān)聽 addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }); // 加入鼠標(biāo)監(jiān)聽 addMouseListener(new MouseAdapter() { public void mouseClicked(MouseEvent e) { Hanio hanio = (Hanio) e.getSource(); Dimension frSize = hanio.getSize(); int x = e.getX(); int w = frSize.width / 3; if (x < w) { hanio.getHanioDraw().click(0); } else if (x < (2 * w)) { hanio.getHanioDraw().click(1); } else { hanio.getHanioDraw().click(2); } hanio.repaint(); } }); // 窗體居中 setLocationRelativeTo(null); // 顯示窗口 setVisible(true); } public void paint(Graphics g) { final int OBJECT_H = 15;// 對(duì)象高 final int OBJECT_W = 10;// 對(duì)象寬 final int OBJECT_D = 90;// 對(duì)象間距 final int OBJECT_S = 60;// 起始位置 // 繪制圖像 int n; for (n = 0; n < 8; n++) { if (_hanioDraw.getBlock(n, 0) != 0) { g.drawRect(OBJECT_S, 200 - n * OBJECT_H, OBJECT_W * _hanioDraw.getBlock(n, 0), OBJECT_H); } } for (n = 0; n < 8; n++) { if (_hanioDraw.getBlock(n, 1) != 0) { g.drawRect(OBJECT_D + OBJECT_S, 200 - n * OBJECT_H, OBJECT_W * _hanioDraw.getBlock(n, 1), OBJECT_H); } } for (n = 0; n < 8; n++) { if (_hanioDraw.getBlock(n, 2) != 0) { g.drawRect(2 * OBJECT_D + OBJECT_S, 200 - n * OBJECT_H, OBJECT_W * _hanioDraw.getBlock(n, 2), OBJECT_H); } } if (_hanioDraw.getTop() != 0) { g.drawRect(60, 60, OBJECT_W * _hanioDraw.getTop(), OBJECT_H); } if (_hanioDraw.goFull()) { g.drawString("完成", 100, 100); } } public HanioDraw getHanioDraw() { return _hanioDraw; } public void setHanioDraw(HanioDraw hd) { this._hanioDraw = hd; } class HanioDraw { private int _top;// 拿起的方塊 private int _size;// 總數(shù) private int[][] _room;// 用以存儲(chǔ)位置 private int[] _cache;// 緩存單個(gè)對(duì)象 public HanioDraw() { _room = new int[8][3]; _cache = new int[3]; // 默認(rèn)初始值 init(3); } /** * 開始處理 * * @param x */ public void init(int x) { _size = x - 1; for (int i = 0; i <= 2; i++) { for (int j = 0; j < 8; j++) { _room[j][i] = 0; } _cache[i] = -1; } for (int i = 0; i < x; ++i) { _room[i][0] = x - i; } _cache[0] = x - 1; _top = 0; } /** * 拿起目標(biāo)對(duì)象 * * @param x * @return */ boolean take(int x) { if (_cache[x] == -1) return false; _top = _room[_cache[x]][x]; _room[_cache[x]][x] = 0; _cache[x]--; return true; } /** * 拖動(dòng)目標(biāo)對(duì)象 * * @param x * @return */ boolean drop(int x) { if (_cache[x] != -1) { if (_top > _room[_cache[x]][x]) return false; } _cache[x]++; _room[_cache[x]][x] = _top; _top = 0; return true; } /** * 判定事件是否完成 * * @return */ public boolean goFull() { if (_cache[1] == _size) { return true; } if (_cache[2] == _size) { return true; } return false; } /** * 點(diǎn)擊事件 * * @param x * @return */ public boolean click(int x) { if (goFull()) { return false; } if (_top == 0) { take(x); } else { drop(x); } return true; } public int getTop() { return _top; } public int getBlock(int x, int group) { return _room[x][group]; } }}運(yùn)行圖如下：
浙公網(wǎng)安備 33010602011771號(hào)