ackerermann1.cpp

动态规划解ＡＣＫＥＲＭＡＮ函数 动态规划解ＡＣＫＥＲＭＡＮ函数

#include<stdio.h>
int ackermann(int,int);
 
void main()
{
       int m,n,result;
       printf("Ackermann(m,n)\nPlease enter m:");
       scanf("%d",&m);
       printf("Please enter n:");
       scanf("%d",&n);
       result=ackermann(m,n);
       printf("the Ackmann(%d,%d) is %d\n",m,n,result);
}

int ackermann(int m,int n)
{
       int i,j;
       int *val=new int[m+1];
       int *ind=new int[m+1];
      for(i=1;i<=m;i++)
      {
              ind[i]=-1;
              val[i]=0;
      }
       ind[0]=0;
       val[0]=1;
       while(ind[m] < n)
       {
              val[0]++;
              ind[0]++;
              printf("%d ",val[0]);
              for(j=1;j<=m;j++)
              {
				  //根据当n=0时，A(m,0)=A(m-1,1)，
				  //又val[i]=A(i,ind[i]),
				  //即当ind[i-1]=1,若有ind[i]=0,可求出val[i]=val[i-1]
                  if(1==ind[j-1])
                  {
                       val[j]=val[j-1];
                       ind[j]=0;
                  }

                  //根据当n>0,m>0时,A(m,n)=A(m-1,A(m,n-1))
				  //又val[i]=A(i,ind[i])
				  //即当ind[i-1]=val[i],ind[i]增1时，相应的val[i]=val[i-1]
                  if(val[j]==ind[j-1])
				  {
					   ind[j]++;
                       val[j]=val[j-1];
				  }
				  else break;
              }
       }//以此不断增大ind[m]的值，不断接近n,直至等于n时，val[m]就是要求的值

       printf("\n");
       printf("    i   ind[i] val[i]\n");
       for(i=0;i<=m;i++)
              printf("%5d %6d %6d\n",i,ind[i],val[i]);
       return val[m];
}