锐客网

  1. 首页 > 睿知 > it技术 > >

java代码递归汉罗塔 汉罗塔递归算法( 二 )

IT技术递归


//反正有人证明过 。i是用来保存最小那个盘子正在哪跟柱子上的 。
int i=0;
for(int k=0;k(int)Math.pow(2, n)-1;){
int min;
//将最小的盘子顺时针移动一个柱子
min = pillars[i%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[i%3]+"-"+pillars[(i+1)%3]);
k++;
i++;
//这个IF好像可以不要，当时写的，后面忘了删除 。
if(k(int)Math.pow(2, n)-1){
//如果 ， 剩下两根柱子中 ， 某一根为空，则一定是非空那根中最上面个盘子
//移动到空的那个柱子上 。若两根都不为空 ， 则把编号小的一个盘子
//移动到另外跟柱子上
if(!pillars[(i-1)%3].isEmpty()(pillars[(i+1)%3].isEmpty()||pillars[(i+1)%3].Top()pillars[(i-1)%3].Top())){
min=pillars[(i-1)%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[(i-1)%3]+"-"+pillars[(i+1)%3]);
}else{
min=pillars[(i+1)%3].Pop();
pillars[(i-1)%3].Push(min);
System.out.println(pillars[(i+1)%3]+"-"+pillars[(i-1)%3]);
}
k++;
}
}
}
//主函数，用来测试的 。3表示3个盘子 。
public static void main(String args[]){
new Hannuota(3).function();
}
}
class Pillar{//构造一个新类，表示柱子，实际是当一个栈在用
private int[] s;
private int top;
private String name;
public String toString(){
return name;
}
//这个构造函数用来构造BC两个柱子 ， 下面那个用来构造柱子A 。其实也可以写成一个构造函数 。
public Pillar(int max,String name){
s = new int[max];
top = -1;
this.name = name;
for(int i=0;imax;i++){
s[i] = max+1;
}
}
public Pillar(int n,int max,String name){
s = new int[max];
top = n-1;
this.name = name;
for(int i=0;imax;i++){
s[i] = max - i;
}
}
//这后面这些就是栈的基本方法了，不用介绍了吧
public boolean isEmpty(){
return top==-1?true:false;
}
public int Top (){
return s[top];
}
public int Pop(){
return s[top--];
}
public void Push(int x){
s[++top] = x;
}
}
算法是这个
首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1 。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上 。
根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B 。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；
若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A 。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上 。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的 。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动 。
这玩意要非递归真麻烦 。需不需要加点注释？
其实我不明白干嘛非要非递归 。。。
求java版汉诺塔的演示程序源代码java代码递归汉罗塔：
/**
*本程序完成的功能是利用汉递规算法实现汉诺塔的动态演示程序
*/
import javax.swing.*;
import java.awt.geom.*;
import java.awt.event.*;
import java.awt.*;
public class Hanio extends JApplet implements ActionListener, Runnable

推荐阅读


上一篇：python中impyla，PYTHON怎么读

下一篇：erp系统由哪个部门管理，erp管理系统有