成都网站建设设计

将想法与焦点和您一起共享

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

}


本文题目:c语言阿克曼函数动态规划 c++阿克曼函数
本文URL:http://chengdu.cdxwcx.cn/article/hjihgs.html