汉诺塔问题[又称河内塔]是印度的一个古老的传说。
据传开天辟地之神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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
但每当增加一阶，移动的次数却会以倍数增加，因此每当圆盘增加到一定数量时，常人只能望而却步。
而我们程序员却可以借助于计算机的运算性能，轻而易举地解决这一问题，汉诺塔问题也作为程序设计中的经典递归问题而存在下来。
但是，实践和理论往往却有天壤之别，我们虽然可以运算出汉诺塔的结果，但是却未必能动手完成这一结果。不信？我这里给出了一个简单的汉诺塔实现，有兴趣的可以自己码盘子看看。
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汉诺塔测试
* </p>
* <p>
* Copyright: Copyright (c) 2007
* </p>
* <p>
* Company: LoonFramework
* </p>
*
* @author chenpeng
* @email：[email]ceponline@yahoo.com.cn[/email]
* @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汉诺塔实现测试", 350, 300);
}
public Hanio(String string, int width, int height) {
super(string);
_hanioDraw = new HanioDraw();
setResizable(false);// 设为用户不可改变窗体大小
setSize(width, height);// 设置窗口大小
setBackground(Color.WHITE);// 背景颜色设置为白色
// 菜单
MenuBar myMenu = new MenuBar();
Menu sMenu = new Menu("选择数量");
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);
// 加入窗体监听
addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
// 加入鼠标监听
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;// 对象高
final int OBJECT_W = 10;// 对象宽
final int OBJECT_D = 90;// 对象间距
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;// 总数
private int[][] _room;// 用以存储位置
private int[] _cache;// 缓存单个对象
public HanioDraw() {
_room = new int[8][3];
_cache = new int[3];
// 默认初始值
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;
}
/**
* 拿起目标对象
*
* @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;
}
/**
* 拖动目标对象
*
* @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;
}
/**
* 点击事件
*
* @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];
}
}
}
运行图如下：
据传开天辟地之神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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
但每当增加一阶，移动的次数却会以倍数增加，因此每当圆盘增加到一定数量时，常人只能望而却步。
而我们程序员却可以借助于计算机的运算性能，轻而易举地解决这一问题，汉诺塔问题也作为程序设计中的经典递归问题而存在下来。
但是，实践和理论往往却有天壤之别，我们虽然可以运算出汉诺塔的结果，但是却未必能动手完成这一结果。不信？我这里给出了一个简单的汉诺塔实现，有兴趣的可以自己码盘子看看。
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汉诺塔测试 * </p> * <p> * Copyright: Copyright (c) 2007 * </p> * <p> * Company: LoonFramework * </p> * * @author chenpeng * @email：[email]ceponline@yahoo.com.cn[/email] * @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汉诺塔实现测试", 350, 300); } public Hanio(String string, int width, int height) { super(string); _hanioDraw = new HanioDraw(); setResizable(false);// 设为用户不可改变窗体大小 setSize(width, height);// 设置窗口大小 setBackground(Color.WHITE);// 背景颜色设置为白色 // 菜单 MenuBar myMenu = new MenuBar(); Menu sMenu = new Menu("选择数量"); 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); // 加入窗体监听 addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }); // 加入鼠标监听 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;// 对象高 final int OBJECT_W = 10;// 对象宽 final int OBJECT_D = 90;// 对象间距 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;// 总数 private int[][] _room;// 用以存储位置 private int[] _cache;// 缓存单个对象 public HanioDraw() { _room = new int[8][3]; _cache = new int[3]; // 默认初始值 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; } /** * 拿起目标对象 * * @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; } /** * 拖动目标对象 * * @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; } /** * 点击事件 * * @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]; } }}
运行图如下：
本文转自 cping 51CTO博客，原文链接:http://blog.51cto.com/cping1982/130095
