汉诺塔问题[又称河内塔]是印度的一个古老的传说。
据传开天辟地之神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着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
但每当增加一阶,移动的次数却会以倍数增加,因此每当圆盘增加到一定数量时,常人只能望而却步。
而我们程序员却可以借助于计算机的运算性能,轻而易举地解决这一问题,汉诺塔问题也作为程序设计中的经典递归问题而存在下来。
但是,实践和理论往往却有天壤之别,我们虽然可以运算出汉诺塔的结果,但是却未必能动手完成这一结果。不信?我这里给出了一个简单的汉诺塔实现,有兴趣的可以自己码盘子看看。
packageorg.loon.test;
importjava.awt.Color;
importjava.awt.Dimension;
importjava.awt.Frame;
importjava.awt.Graphics;
importjava.awt.Menu;
importjava.awt.MenuBar;
importjava.awt.MenuItem;
importjava.awt.event.ActionEvent;
importjava.awt.event.ActionListener;
importjava.awt.event.MouseAdapter;
importjava.awt.event.MouseEvent;
importjava.awt.event.WindowAdapter;
importjava.awt.event.WindowEvent;
/***//**
*<p>
*Title:LoonFramework
*</p>
*<p>
*Description:java汉诺塔测试
*</p>
*<p>
*Copyright:Copyright(c)2007
*</p>
*<p>
*Company:LoonFramework
*</p>
*
*@authorchenpeng
*@email:ceponline@yahoo.com.cn
*@version0.1
*/
publicclassHanioextendsFrame...{
/***//**
*
*/
privatestaticfinallongserialVersionUID=1L;
privateHanioDraw_hanioDraw;
publicstaticvoidmain(Stringargs[])...{
newHanio("java汉诺塔实现测试",350,300);
}
publicHanio(Stringstring,intwidth,intheight)...{
super(string);
_hanioDraw=newHanioDraw();
setResizable(false);//设为用户不可改变窗体大小
setSize(width,height);//设置窗口大小
setBackground(Color.WHITE);// 背景颜色设置为白色
//菜单
MenuBarmyMenu=newMenuBar();
MenusMenu=newMenu("选择数量");
MenuItem[]mItems=newMenuItem[6];
for(inti=3;i<=8;i++)...{
mItems[i-3]=newMenuItem(String.valueOf(i));
mItems[i-3].addActionListener(newActionListener()...{
publicvoidactionPerformed(ActionEvente)...{
_hanioDraw.init(Integer.parseInt(((MenuItem)e.getSource())
.getLabel().toString()));
repaint();
}
});
sMenu.add(mItems[i-3]);
}
myMenu.add(sMenu);
setMenuBar(myMenu);
setLayout(null);
//加入窗体监听
addWindowListener(newWindowAdapter()...{
publicvoidwindowClosing(WindowEvente)...{
System.exit(0);
}
});
//加入鼠标监听
addMouseListener(newMouseAdapter()...{
publicvoidmouseClicked(MouseEvente)...{
Haniohanio=(Hanio)e.getSource();
DimensionfrSize=hanio.getSize();
intx=e.getX();
intw=frSize.width/3;
if(x<w)...{
hanio.getHanioDraw().click(0);
}elseif(x<(2*w))...{
hanio.getHanioDraw().click(1);
}else...{
hanio.getHanioDraw().click(2);
}
hanio.repaint();
}
});
//窗体居中
setLocationRelativeTo(null);
//显示窗口
setVisible(true);
}
publicvoidpaint(Graphicsg)...{
finalintOBJECT_H=15;//对象高
finalintOBJECT_W=10;//对象宽
finalintOBJECT_D=90;//对象间距
finalintOBJECT_S=60;//起始位置
//绘制图像
intn;
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);
}
}
publicHanioDrawgetHanioDraw()...{
return_hanioDraw;
}
publicvoidsetHanioDraw(HanioDrawhd)...{
this._hanioDraw=hd;
}
classHanioDraw...{
privateint_top;//拿起的方块
privateint_size;//总数
privateint[][]_room;//用以存储位置
privateint[]_cache;//缓存单个对象
publicHanioDraw()...{
_room=newint[8][3];
_cache=newint[3];
//默认初始值
init(3);
}
/***//**
*开始处理
*
*@paramx
*/
publicvoidinit(intx)...{
_size=x-1;
for(inti=0;i<=2;i++)...{
for(intj=0;j<8;j++)...{
_room[j][i]=0;
}
_cache[i]=-1;
}
for(inti=0;i<x;++i)...{
_room[i][0]=x-i;
}
_cache[0]=x-1;
_top=0;
}
/***//**
*拿起目标对象
*
*@paramx
*@return
*/
booleantake(intx)...{
if(_cache[x]==-1)
returnfalse;
_top=_room[_cache[x]][x];
_room[_cache[x]][x]=0;
_cache[x]--;
returntrue;
}
/***//**
*拖动目标对象
*
*@paramx
*@return
*/
booleandrop(intx)...{
if(_cache[x]!=-1)...{
if(_top>_room[_cache[x]][x])
returnfalse;
}
_cache[x]++;
_room[_cache[x]][x]=_top;
_top=0;
returntrue;
}
/***//**
*判定事件是否完成
*
*@return
*/
publicbooleangoFull()...{
if(_cache[1]==_size)...{
returntrue;
}
if(_cache[2]==_size)...{
returntrue;
}
returnfalse;
}
/***//**
*点击事件
*
*@paramx
*@return
*/
publicbooleanclick(intx)...{
if(goFull())...{
returnfalse;
}
if(_top==0)...{
take(x);
}else...{
drop(x);
}
returntrue;
}
publicintgetTop()...{
return_top;
}
publicintgetBlock(intx,intgroup)...{
return_room[x][group];
}
}
}
运行图如下:
分享到:
相关推荐
就是一个用Java写的汉诺塔小游戏,大家测试下,有用到回溯和简单的线程。
定义一个类实现银行账户的概念。包括的属性有“账号”和“存款余额”,包括的方法有“存款”、“取款”、“查询余额”...编写一测试类,创建两个不同的账户类的对象,并分别完成存款、取款、查询余额、显示账号等操作。
用java写的项目,源码都经测试过,真实可靠,欢迎自行下载学习。用java写的项目,源码都经测试过,真实可靠,欢迎自行下载学习。用java写的项目,源码都经测试过,真实可靠,欢迎自行下载学习。用java写的项目,源码...
适用工作项目、毕业设计,课程设计,项目源码均经过助教老师测试,运行无误,欢迎下载 ----- 下载后请首先打开README.md文件(如有)
【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。...
汉诺塔java源码语言基准 这个项目适合所有对几种编程语言的性能差异感兴趣的人。 它还可以用于比较多种语言的语法。 作为奖励,还包括一些函数式逻辑编程语言。 目前基准支持: C C++ 目标-C C# D 帕斯卡 Java ...
【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。...
【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。...
【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。...