问一个关于ackermann函数的递归解决方案问题.

Question

算法定义：A(1, j) =2的j次方    j>=1A( i, 1) = A(i-1,2)    j>=2A(i,j) = A(i-1,A(i, j-1)) i,j>=2要求设计ackermann（int m,int n)使用递归实现该算法我写的算法在算A(3,2)的时候出现了java.lang.StackOverflowError错误,应该是不正确的.为了避免误导大家所以我没有贴上来.
 
a(1,1) = 2
a(2,1) = 4
a(1,2) = 4
a(2,2) = 16
a(2,3) = 65536
a(3,2) = ??
.....哪位递归达人能帮忙解决一下啊?谢谢,每段代码我都会运行都会试.谢谢

Answer 1

对于ackermann函数来说,可能有不同版本的递归定义,这里只针对这个定义.

Answer 2

这样？
A(i,j){
  if(i<=0 || j<=0)return 0;
  else if(i==1)return 2^j;
  else if(j==1)return A(i-1,2);
  else return A(i-1,A(i,j-1));
}

Answer 3

答:问题的根源是你的ackermann(i,j)的定义是不完整引起的.
理由是:按你的ackermann(i,j)的定义写的递归代码如下
代码:public class Ackermann {
private static long pow2(long n)
{
long s=1;
for(int i=1;i<=n;i++)  s=s*2;
return s;
}

 public static long ackermann(long i,long j)
 {
 if(i<1 || j < 1) {
 System.out.println("ackermann计算过程中参数有错:i="+i+" j="+j);
 System.exit(-1);
 
 }
 if(i==1 && j>=0) return  pow2(j);
 if(j==1) return ackermann(i-1,2);
 return ackermann(i-1,ackermann(i,j-1));
 }

public static void main(String[] args) {
// TODO Auto-generated method stub
     System.out.print("ackermann(1,1)=");
     System.out.println(ackermann(1,1));
     System.out.print("ackermann(2,1)=");
     System.out.println(ackermann(2,1));
     System.out.print("ackermann(1,2)=");
     System.out.println(ackermann(1,2));
     System.out.print("ackermann(2,2)=");
     System.out.println(ackermann(2,2));
     System.out.print("ackermann(2,3)=");
     System.out.println(ackermann(2,3));
     System.out.print("ackermann(3,2)=");
     System.out.println(ackermann(3,2));     
}}程序运行结果是:
ackermann(1,1)=2
ackermann(2,1)=4
ackermann(1,2)=4
ackermann(2,2)=16
ackermann(2,3)=65536
ackermann(3,2)=ackermann计算过程中参数有错:i=1 j=0

Answer 4

对对对...我也是类似这么写的..咱俩前几个值算的都一样..
我也在网上查了,对于阿克曼函数来说,貌似是有不同的定义.
但是,我始终没有敢怀疑书上的定义有问题.呵呵另一种定义是这样的.
A(1,0) = 2
A(0,m) = 1        m>=0
A(n,0) = n + 2    n>=2
A(n,m) = A(A(n-1,m),m-1)  n,m >= 1public static long ackermann(long m, long n) {
    if(m==0) {
        if(n==0) {
            return 1;
        }
        else if (n == 1) {
            return 2;
        }
        else {
            return n + 2;
        }
    }
    else {//m>=1
        if(n==0) {
            return 1;
        }
        else {//n>=1
            return ackermann(ackermann(n-1,m),m-1);
        }
    }
}但是这样写到ackermann(3,2)时,还是出现了java.lang.StackOverflowError错误

Answer 5

答:你的新版本的阿克曼函数定义就好些,代码如下:
public class Ackermann {



 public static long ackermann(long i,long j)
 {
 if(i<0 || j < 0) {
 System.out.println("ackermann计算过程中参数有错:i="+i+" j="+j);
 System.exit(-1);  
 }
 if(i==1 && j==0) return  2;
 if(i==0 ) return 1;
 if(i>=2 && j==0 ) return i+2;
 return ackermann(ackermann(i-1,j),j-1);
 }

public static void main(String[] args) {
// TODO Auto-generated method stub
     System.out.print("ackermann(1,1)=");
     System.out.println(ackermann(1,1));
     System.out.print("ackermann(2,1)=");
     System.out.println(ackermann(2,1));
     System.out.print("ackermann(1,2)=");
     System.out.println(ackermann(1,2)); 
     System.out.print("ackermann(2,2)=");
     System.out.println(ackermann(2,2));
     System.out.print("ackermann(2,3)=");
     System.out.println(ackermann(2,3));
     System.out.print("ackermann(3,2)=");
     System.out.println(ackermann(3,2));   
    
}}
程序运行结果:
ackermann(1,1)=2
ackermann(2,1)=4
ackermann(1,2)=2
ackermann(2,2)=4
ackermann(2,3)=4
ackermann(3,2)=8看来不同定义的版本,值还不一样呢.

Answer 6

我觉得这个ackermann函数真的可以说是迷一样的...感觉有些东西想搞明白真的非常的不容易啊.谢谢云上飞翔对我的帮助,结贴了..