c语言阿克曼函数动态规划 c++阿克曼函数

C++ 关于阿克曼函数的伪非递归算法 编个C++程序 不用递归怎么做？写出程序

非递归可以用自底向上bottom-up动态规划的方法，递归属于自顶向下，与之正好相反：

创新互联-专业网站定制、快速模板网站建设、高性价比庐阳网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式庐阳网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖庐阳地区。费用合理售后完善，十余年实体公司更值得信赖。

int Ackermann(int m,int n)

{

int akm[m][n];

int i,j;

memset(akm,o,sizeof(akm));

for(j=0;jn;j++)

akm[0][j]=j+1;

for(i=1;im;i++)

{

akm[0]=akm[i-1][1];

　for(j=1;jn;j++)

{

akm[j]=akm[i-1][akm[j-1]];

　}

}

return akm[m][n];

}

堆栈的也对百科上也有

利用递归法求阿克曼函数

这里给出C语言的阿克曼递归函数：首先，阿克曼函数标准定义：#include stdio.h

#include stdlib.hint Ackmann(int n,int m)

{

if(m==0)return n+1;

else if(m0 n==0)return Ackmann(m-1,1);

else return Ackmann(m-1,Ackmann(m,n-1));

}int main()

{

int m,n;

printf("输入m和n：");

scanf("%d,%d",m,n);

printf("结果是：%d",Ackmann(n,m));

system("pause");

return 0;

}

Ackerman函数的动态规范算法

试设计一个计算A(m，n)的动态规划算法，该算法只占用O(m)空间。

用两个一维数组，ind[i]和val[i]，使得当ind[i]等于t时，val[i]=A(i，ind[i])。

i ind[i] val[i]

0 0 1

1 -1 0

2 -1 0

……

初始时，令ind[0]=0，val[0]=1，ind[i]=-1(i0)，val[i]=0(i0)。

1当m=0时，A(m，n)=n+1。

任给一个t，当ind[0]=t时，能够求出val[0]的值，val[0]等于ind[0]。

2当n=0，m0时，A(m，n)=n+1。

能够求出当ind[i]=0时，val[i]的值，此时val[i]等于当ind[i-1]等于1时val[i-1]的值。

3当m0，n0时，A(m，n)=A(m-1，A(m，n-1))。

当ind[i]=t，val[i]=s时，要求当ind[i]’=t+1时val[i]’的值。

Val[i]’=A(i，ind[i]’)=A(i-1，A(i，ind[i]’-1)=A(i-1，A(i，ind[i]))=A(i-1，val[i])

所以，当ind[i-1]=val[i]时，能够求出当ind[i]’=k+1时，val[i]’=val[i-1]。

#include stdio.h

int ack(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]=-1;

}

ind[0]=0;

val[0]=1;

while(ind[m]n)

{

val[0]++;

ind[0]++;

printf("%d ",val[0]);

for(j=1;j=m;j++)

{

if(1==ind[j-1])

{

val[j]=val[j-1];

ind[j]=0;

}

if(val[j]!=ind[j-1])

break;

ind[j]++;

val[j]=val[j-1];

}

}

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];

}