ackermann.java

自己编写的几个动态规划算法的例子

/*
 * Ackermann.java  Created by JoyChou
 *借助两个一维数组val[0:m]和ind[0:m](其中对任何i都有val[i]=A(i,ind[i]) )
 *使用动态规划思想，自底向上计算A(m,n),避免了重复计算
 */
package ackermann;
import java.io.*;
import java.lang.*;

public class Ackermann {    
       /* @param args the command line arguments   */
    public static void main(String[] args) throws IOException {
         /* Give the value of A(m,n) */
        int m,n;
       
        System.out.println("This programme will tell you the value of A(m,n) ! ");
        System.out.println("First,please input the value of  'm' and ' n'  : ");
        System.out.print("m = ");
        
        BufferedReader myIn =new BufferedReader(new InputStreamReader(System.in));
        m = Integer.parseInt(myIn.readLine());
        System.out.print(m);
        System.out.print(" ; n = ");
        n = Integer.parseInt(myIn.readLine());
        System.out.println(n);   
        
        int val[] = new int [m+1] ;
        int ind[] = new int [m+1] ;
        //initialization
        for ( int i =0 ;i<=m ;i++ )
        {
            val[i] = 0;
            ind[i] = -1; 
        }
        //the original data,A(0,1) = 2
        val[0] = 2 ;
        ind[0] = 1 ;
        int depth = 0;
        while( ind[m] != n)
        {
            // when ( m>0) and ( n=0 ) , A(m,0) = A(m-1,1)
            if( (ind[depth]==1) && (depth < m) ){
                val[depth+1] = val[depth] ;
                ind[depth+1] = 0;
                depth++;
            }          
            //when (m>0) and (n>0) ,A(m,n) = A( m-1,A(m,n-1) )
            while( ind[depth-1] < val[depth] ){
                ind[0]++;
                val[0] = ind[0]+1;
                for(int i=0;i<depth-1;i++)
                    if(ind[i] == val[i+1]){      //A(m,n)=A(m-1,A(m,n-1))
                       val[i+1]=val[i];
                       ind[i+1]++;
                    }
            }
            val[depth]=val[depth-1]; //A(m,n)=A(m-1,A(m,n-1))
            ind[depth]++;
        }
        System.out.println("The result is :  A("+m+","+n+")="+val[m]);   
    }
}