JAVA编程问题：求汉诺塔非递归JAVA代码

Question

如题，递归的已经让我很头痛了，实现想不出非递归的出来，麻烦高人指点！！！
这个还是递归啊，书上说尝试一下用非递归的，我想看哪位高人用非递归的写出来了。 去网上搜索了一下，只看到C++的，看不懂

Answer 1

public class Hannuota {
private int n;//储存盘子个数
public Hannuota(int n){
this.n = n;
}
public void function(){
//初始化三个柱子，A是开始堆满盘子的柱子，C是目标柱子
Pillar a = new Pillar(n,n,"A");
Pillar b = new Pillar(n,"B");
Pillar c = new Pillar(n,"C");
//把三个柱子按顺序排好，详见后面的算法那里的解释
Pillar[] pillars = new Pillar[3];
pillars[0] = a;
if(n%2==0){
pillars[1] = b;
pillars[2] = c;
}else{
pillars[1] = c;
pillars[2] = b;
}
//开始移动，k用来计数，移动次数为2^n-1,至于为什么，我不太清楚，
//反正有人证明过。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;i<max;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;i<max;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）操作，最后就能按规定完成汉诺塔的移动。

这玩意要非递归真麻烦。需不需要加点注释？
其实我不明白干嘛非要非递归。。。

Answer 2

public class Hang{
public void h(int n,char A,char B,char C){
if(n==1){
System.out.println(1+":"+A+"->"+B+"->"+C);

}
else{
h(n-1,A,C,B);
System.out.println(n+":"+A+"->"+B+"->"+C);
h(n-1,C,B,A);

}

}
public static void main(String args[])throws Exception{

new Hang().h(3,'A','B','C');
}
}

这难道不是递归啊 昏

Answer 3

非递归？你疯了，肯定要递归的，游戏啊！这是经典的算法！