ArrayList实现Ackerman非递归算法

Ackerman(m,n)函数的递归定义为

public static int ackerman(int a,int b){
   if(a==0)
      return b+1;
   else if(a!=0&&b==0)
      return ackerman(a-1,1);
   else
      return ackerman(a-1,ackerman(a,b-1));
}

递归转换为非递归需要使用栈来模拟递归
那么就选用ArrayList充当下栈吧,对我来说用起来比较熟悉,你可以使用java自己的Stack类

栈结构为
m n result

把它写成一个bean作为我们的栈的一个小块

class Stack{
	private int m;
	private int n;
	private int result;
	
	public Stack(int m,int n,int result){
		this.m=m;
		this.n=n;
		this.result=result;
	}
	get/set()方法省略	
}

n或result=-1时代表解暂时未得到

下面是实现算法的主要思想

while(栈非空&&没有得到答案){
    取栈顶对象stacktemp
    if(该元素.result还没有解){
        if(m和n都!=0){
           //因为Ackerman在这个情况下会分解成2个函数，所以都要进栈
             new stack1(m-1,-1,-1)进栈
             new stack2(m,n-1,-1)进栈
             ArrayList.add(stack1和stack2);
        }
        else if(n==0){
           //这个情况下只分解为一个函数
             new stack(m-1,1,-1)进栈
        }
        else if(m==0){
            //这个情况可以得到stacktemp的结果,即n+1;
            修改stacktemp的result
         }
    }
    //如果的到的stacktemp是有解的进行出栈动作
    else{
       if(栈的长度==1){
          //说明得到我们的结果了
            得到结果
            设置一个flag让循环可以终止
       }
       if(stacktemp.m为0){
           将stacktemp.result传给上一个栈的result
           stacktemp出栈
       }
       else if(stacktemp.m!=0){
           if(如果上一个栈的n==-1){
                该元素的结果传给上一个栈的n
                stacktemp出栈
            }
            else{
                 //这是关键点，因为Ackerman函数是双递归,需要递归2次，这个else恰好是2个分支的交汇处
                 将stacktemp.result传给上一个栈的result
                 stacktemp出栈
            }
       }
    }
}

完整代码如下

package com.datastructure;

import java.util.ArrayList;
import java.util.Calendar;

public class AckermanWithoutCycle {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自动生成方法存根
		int result=-1;
		boolean gotAnswer=false;
		long starttime=-1;
		long endtime=-1;
//		System.out.println("请输入Ackerman的2个参数");
//		Scanner sc=new Scanner(System.in);
//		int a=sc.nextInt();
//		int b=sc.nextInt();
		int a=4;
		int b=1;
		ArrayList<Stack> stacklist=new ArrayList<Stack>();
		Stack stack=new Stack(a,b,-1);
		stacklist.add(stack);
		starttime=Calendar.getInstance().getTimeInMillis();
		while(stacklist.size()>0&&!gotAnswer){
			//取栈顶元素
			Stack stacktemp=stacklist.get(stacklist.size()-1);
			//如果该元素还没有解
			if(stacktemp.getResult()==-1){	
				if(stacktemp.getM()!=0&&stacktemp.getN()!=0){
					Stack stack1=new Stack(stacktemp.getM()-1,-1,-1);
					Stack stack2=new Stack(stacktemp.getM(),stacktemp.getN()-1,-1);
					stacklist.add(stack1);
					stacklist.add(stack2);
				}
				else if(stacktemp.getN()==0){
					Stack stack1=new Stack(stacktemp.getM()-1,1,-1);
					stacklist.add(stack1);
				}
				//如果m==0那么该栈的解是n+1
				else if(stacktemp.getM()==0&&stacktemp.getN()!=-1){
					stacktemp.setResult(stacktemp.getN()+1);
				}
			}
			//如果该元素有解
			else{
				if(stacklist.size()==1){
					result=stacktemp.getResult();
					gotAnswer=true;
					endtime=Calendar.getInstance().getTimeInMillis();
					break;
				}
				//如果m为0
				if(stacktemp.getM()==0){
					//讲该元素的结果传给上一个栈的result
					stacklist.get(stacklist.size()-2).setResult(stacktemp.getResult());
					stacklist.remove(stacktemp);
				}
				//如果不为0
				else if(stacktemp.getM()!=0){
					//如果上一个栈的n==-1,该元素的结果传给上一个栈的n
					if(stacklist.get(stacklist.size()-2).getN()==-1){
						stacklist.get(stacklist.size()-2).setN(stacktemp.getResult());
						stacklist.remove(stacktemp);
					}
					else{
						stacklist.get(stacklist.size()-2).setResult(stacktemp.getResult());
						stacklist.remove(stacktemp);
					}
				}
			}
		}
		System.out.println("结果为:"+result+"耗时"+(endtime-starttime)+"ms");
	}
}
class Stack{
	private int m;
	private int n;
	private int result;
	
	public Stack(int m,int n,int result){
		this.m=m;
		this.n=n;
		this.result=result;
	}
	public int getM() {
		return m;
	}
	public void setM(int m) {
		this.m = m;
	}
	public int getN() {
		return n;
	}
	public void setN(int n) {
		this.n = n;
	}
	public int getResult() {
		return result;
	}
	public void setResult(int result) {
		this.result = result;
	}
	
}