正文
hanoi塔java代码 hanoi塔递归算法java
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
用java编写hanoi塔的非递归算法。
这是个好问题，很少看到有人写汉诺塔的非递归...其实只要先写出递归，然后把递归的每一步要做的事情记录在一个栈里面就可以了
public class Test {
private static void emitStep(int source, int dest) {
System.out.println(source + " - " + dest);
}
static class Step {
Step(int n, int s, int d, int t) {
this.n = n;
source = s;
dest = d;
temp = t;
}
int n, source, dest, temp;
}
private static void hanoi(int n, int source, int dest, int temp) {
java.util.StackStep steps = new java.util.StackStep();
steps.add(new Step(n, source, dest, temp));
while (steps.empty() == false) {
Step step = steps.pop();
if (step.n == 1) {
emitStep(step.source, step.dest);
continue;
}
steps.push(new Step(step.n - 1, step.temp, step.dest, step.source));
steps.push(new Step(1, step.source, step.dest, 0));
steps.push(new Step(step.n - 1, step.source, step.temp, step.dest));
}
}
public static void main(String[] args) {
hanoi(3, 1, 3, 2);
}
}
相关问答
Q1: java新手汉诺塔问题最终的输出结果如下（问题规模为3），其中盘子的编号是汉诺塔问题中从上到下的顺序。
try..catch用于捕获initProperties()和init()这两个方法执行时候的异常，至于initProperties()和init()这两个方法为何会出异常，就看你具体的业务逻辑了。
try中的代码块儿如果一旦出现异常则在catch中进行捕获，showMessageDialog是JOptionPane封装或者说提供的一个显示一个带有确定按钮的模态对话框的方法。
几个参数中
"Failed to init.\n" + ex 也就是第二个参数是消息框弹出消息的内容。
"BinaryRain 也就是第三个参数是消息框的标题。
JOptionPane.ERROR_MESSAGE 也就是第四个参数，是消息框的类型，表示错误提示，弹出来的消息框有个红色的叉叉标识，如JOptionPane.WARNING_MESSAGE，表示警告提示，弹出来的消息框有个叹号标识。
Q2: 求java版汉诺塔的演示程序
源代码：
/**
*本程序完成的功能是利用汉递规算法实现汉诺塔的动态演示程序
*/
import javax.swing.*;
import java.awt.geom.*;
import java.awt.event.*;
import java.awt.*;
public class Hanio extends JApplet implements ActionListener, Runnable
{
/**
*diskNum是盘子的数量
*/
private int diskNum ;
/**
*各个组件的句柄
*/
private JButton begin, stop;
private JLabel lDiskNum;
private JTextField text;
JPanel pane;
/**
*定义一个线程句柄
*/
private Thread animate;
/**
*定义a,b,c三个柱子上是否有盘子，有哪些盘子
*/
private int adisk[];
private int bdisk[];
private int cdisk[];
public void init()
{
Container content = getContentPane();
content.setLayout(new BorderLayout());
lDiskNum = new JLabel(盘子的数目);
text = new JTextField(8);
begin = new JButton(开始);
begin.addActionListener(this);
stop = new JButton(停止);
stop.addActionListener(this);
pane = new JPanel();
pane.setLayout(new FlowLayout());
pane.add(lDiskNum);
pane.add(text);
pane.add(begin);
pane.add(stop);
content.add(pane, BorderLayout.SOUTH);
}
public void paint(Graphics g)
{
Graphics2D g2D = (Graphics2D)g;
Ellipse2D.Double ellipse;
g2D.setPaint(getBackground());
if(adisk != null)
{
/**
*消除以前画的盘子
*/
for(int j=adisk.length, i=0; --j=0; i++ )
{
ellipse = new Ellipse2D.Double(20+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
ellipse = new Ellipse2D.Double(220+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
ellipse = new Ellipse2D.Double(420+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
}
drawEllipse(g, 20, adisk);//画A组盘子
drawEllipse(g, 220, bdisk);//画B组盘子
drawEllipse(g, 420, cdisk);//画C组盘子
}
pane.repaint();
}
public void update(Graphics g)
{
paint(g);
}
/**画出椭圆代表盘子，g是图形环境，x是最下面的盘子的横坐标，
*arr是柱子数组
*/
public void drawEllipse(Graphics g,int x,int arr[])
{
Graphics2D g2D = (Graphics2D)g;
Ellipse2D.Double ellipse;
g2D.setPaint(Color.gray);
g2D.draw(new Line2D.Double(x+90, 10, x+90, 180));
for(int j=arr.length, i=0; --j=0; i++ )
if(arr[j] != 0)
{
if(i%2 == 0)
g2D.setPaint(Color.blue);
else
g2D.setPaint(Color.red);
ellipse = new Ellipse2D.Double(x+i*5, 180-i*10, 180-i*10, 20);
g2D.fill(ellipse);
}
}
public void actionPerformed(ActionEvent e)
{
String command = e.getActionCommand();
if(command.equals(开始))
{
/**
*进行初始化，开始的时候只有a柱子上有盘子，其他柱子都没有
*/
diskNum = Integer.parseInt(text.getText());
adisk = new int[diskNum];
for(int i=0; iadisk.length; i++)
adisk[i] = 1;
bdisk = new int[diskNum];
for(int k=0; kbdisk.length; k++)
bdisk[k] = 0;
cdisk = new int[diskNum];
for(int i=0; icdisk.length; i++)
cdisk[i] = 0;
repaint();
if(animate == null || !animate.isAlive())//创建一个线程
{
animate = new Thread(this);
animate.start();
}
}
if(command.equals(停止))
{
for(int k=0; kbdisk.length; k++)
bdisk[k] = 0;
for(int i=0; icdisk.length; i++)
cdisk[i] = 0;
repaint();
text.setText();
animate = null;
}
}
/**
*线程方法，在此调用汉诺塔执行移动盘子操作
*/
public void run()
{
hanio(diskNum, 'A', 'B', 'C');
repaint();
}
/**
*汉诺塔递规调用程序，n是盘子的数量，A，B，C分别代表三个柱子
*/
public void hanio(int n, char A, char B, char C)
{
if(n 1)
{
hanio(n-1, A, C, B);
pause();//停顿几秒在执行
switch(A)
{
case 'A':adisk[n-1] = 0;break;
case 'B':bdisk[n-1] = 0;break;
case 'C':cdisk[n-1] = 0;break;
default:break;
}
switch(C)
{
case 'A':adisk[n-1] = 1;break;
case 'B':bdisk[n-1] = 1;break;
case 'C':cdisk[n-1] = 1;break;
default:break;
}
repaint();
hanio(n-1, B, A, C);
}
pause();
switch(A)
{
case 'A':adisk[n-1] = 0;break;
case 'B':bdisk[n-1] = 0;break;
case 'C':cdisk[n-1] = 0;break;
default:break;
}
switch(C)
{
case 'A':adisk[n-1] = 1;break;
case 'B':bdisk[n-1] = 1;break;
case 'C':cdisk[n-1] = 1;break;
default:break;
}
repaint();
}
/**
*每隔半妙钟移动一个盘子
*/
public void pause()
{
try{
Thread.sleep(500);//可以修改此值加快盘子移动的速度
}catch(InterruptedException e){}
}
}
Q3: JAVA程序归递算法求解汉诺塔问题
首先你需要有下面这两个意识：
1.一个函数对于其它函数来说相当于一个盒子，他封装了其中的内容，其它函数只知道给它参数，然后得到它的结果。就好比一个做蛋糕的商店：我们只需要知道给钱，它就会给蛋糕。而我们不需要理解他们是怎么做出来的这个蛋糕。
2.调用的过程，就相当于上面例子中我们去买蛋糕的过程。谁说自己不能买自己店里的蛋糕呢？比如你是做蛋糕的，难道你不能买自己店里的蛋糕吗？函数的自我调用（递归？）也是这么回事情。
对于hanoi类里面，两个核心函数：
move（char getme, char purone):
这个函数的功能是：把getme最上面的盘子移动到purone位置，比如
move('A','B')就是把A柱子最上面那个盘子移动到B柱子的最上面。
hanoi(int n,char one,char two,char three）：
这个函数的功能是：现在在柱子one上一共有n个盘子，这个函数能够通过two把它移动到three上面。
现在你了解了这两个函数设计的初衷，ok，我们来分别实现每个函数。
public void move(char getme,char purone)
{//请联系上面写的这个函数的功能来看：
c=c+1;//我们每移动一步，就计数一次
System.out.println(getme+"--"+putone+"搬盘次数为："+c);
//这行使用输出来表明移动过了（事实上hanoi就是要让你详细说明移动过程，所谓“说明”，就是打印出每次的移动，那这里我们就把这次移动打印出来，这个没有任何问题吧？这个函数就是要把移动这件事情说出来，明白？
}
public void hanoi(int n,char one,char two,char three)
{//请回忆hanoi函数的功能，是要把one柱子上的前n个放到three柱子上：
if(n==1) //如果n==1,那也就是要把one柱子上最上面的那个移到three上面了，这就是move函数的作用，对吧？那就直接调用move(one,three)
move(one,three);
else{
//如果n1的话，那我们该怎么办？
分为三个步骤：
1.先想办法把one主子上的前n-1个移动到柱子two上
2.然后把one柱子上的第n个移动到柱子three上。
3.然后想办法把two柱子上的n-1个移动到three上。
对吧？现在你注意到第1步和第3步是不是就是hanoi这个函数的功能能够实现的呢？回答显然是肯定的，下面就是这三步。
hanoi(n-1,one,three,two); //把one柱子上的n-1个通过three移动到two上。
move(one,three); //把one主子上最上面那个（注意，上面一步已经把前n-1个移动到two上面了，one柱现在最上的那个就是第N个）
hanoi(n-1,two,one,three);//把two柱子上的n-1个移动到three柱子上。
}
}
解释到这里，main函数里面的调用应该也就很明白了吧？
a.hanoi(m,'A','B','C')；
把'A'柱子上的m个盘子通过'B'柱子全部移动到'C'上面的步骤。
解释起来很容易，想得多了也就慢慢明白了，最难的是如何设计一个递归出来。这个和数学里面的递推公式很相似（事实上其来源就是递推公式），想必你肯定知道递增函数把？ An = An-1 + 5（A0 = 0 );这个条件能够唯一确定一个数列。
那现在你把它写成函数呢？
int A(int n) {
if(n == 0) {
return 0;
} else {
return A(n -1) + 5;
}
}
调用A(n)就能返回An的值。明白？
多想想，多练练，大家都是这么过来的：）祝好运
Q4: JAVA汉诺塔
import java.awt.*;
public class TowerPoint //公共类TowerPoint
{
int x,y; //定义2个int类型的变量
boolean 有盘子; //定义一个boolean类型的变量
Disk 盘子=null; //初始化一个对象"盘子"并赋值为空
HannoiTower con=null; //初始化一个HannoiTower类的对象"con"并赋值为空
public TowerPoint(int x,int y,boolean boo) //构造函数，有3个参数，x，y，boo
{
this.x=x; //将参数赋给当前x
this.y=y; //将参数赋给当前y
有盘子=boo; //将boo赋给"有盘子"
}
public boolean 是否有盘子() //定义一个返回boolean类型的方法"是否有盘子"
{
return 有盘子; //返回boolean类型的"有盘子"
}
public void set有盘子(boolean boo) //set方法，并且参数为boolean
{
有盘子=boo; //将boo赋给有盘子
}
public int getX() //取得x方法
{
return x; //返回x
}
public int getY()//取得y方法
{
return y; //返回y
}
public void 放置盘子(Disk 盘子,HannoiTower con) //定义一个有2个参数的"放置盘子"方法。参数是Disk类和HannoiTower类
{
this.con=con; //当前con等于参数con
con.setLayout(null); //调用on对象的方法setLayout，并设置为空
this.盘子=盘子; //当前盘子等于参数盘子
con.add(盘子); //con对象的add方法，加入"盘子"对象
int w=盘子.getBounds().width; //定义并给一个int类型的w变量一个值，值为"盘子.getBounds().width"
int h=盘子.getBounds().height; //定义并给一个int类型的h变量一个值，值为"盘子.getBounds().height"
盘子.setBounds(x-w/2,y-h/2,w,h);//调用"盘子"对象的setBounds方法，并把传递值
有盘子=true;//boolean类型的对象"有盘子"等于true
con.validate(); //调用con对象的validate方法
}
public Disk 获取盘子() //定义"获取盘子"方法，方法返回Disk对象
{
return 盘子; //返回盘子
}
}
-----------------------另外说一下，楼主太抠门了！！！！！！！！只给5分-----------------------
Q5: java中汉诺塔的算法问题
class HanRuoTa {
static long s=0;
public static void main(String args[]) {
int n =3;
System.out.println("汉诺塔层数为" + n);
System.out.println("移动方案为：" );
hanoi(n, 'a', 'b', 'c');
System.out.println("需要移动次数："+s);
}
static void hanoi(int n, char a, char b, char c) {
if (n 0) {
hanoi(n - 1, a, c, b);
move(a, b);
hanoi(n - 1, c, b, a);
s++;
}
}
static void move(char x, char y) {
System.out.println(x + "-" + y + "\t");
}
}
运行结果：
汉诺塔层数为3
移动方案为：
a-b
a-c
b-c
a-b
c-a
c-b
a-b
需要移动次数：7
