Ackermann函数算法分析与设计2.ppt

题目 Ackermann函数A(m,n)可递归定义如下： 试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。（提示：用两个数组val[0:m]和int[0:m],使得对任何i有val[i]=A(i,ind[i]))。 对于较小的m和n，Ackermann函数A(m,n)的值如图 从图中可以看出 当m=0时，第0行对应于A(0,n)的值； 当n=0时，第0列对应于A(m,0)的值，其值恰好是第m-1行第1列的值； A(m,n)的值等于第m-1行第A(m,n-1)列的值； 据此，可从第一行的值依次递推出各行的值。 递归方法 int ackermann(int m,int n) { if(m==0) return n+1; if(n==0)return ackermann(m-1,1); else return ackermann(m-1,ackermann(m,m-1)); } 用备忘录方法实现 使用一个二维数祖A[1..m,1..n]记录所有的ackermann函数值； 初始的时候全部填充-1，表示尚未计算过； 然后直接用递归函数计算ackermann函数 ； 在递归计算之前，现判断数组A中该函数值是否已被计算过，如果计算过了则直接从数组A中取出结果，不要再做重复计算；如果没有计算过，则递归计算。 大致算法过程: Ackermann(m,n) if m=0 then return A[m,n]=n+1; elseif m0 and n=0 then return A[m,n]=A(m-1,1); elseif m0 and n0 then A[m,n]=A(m-1,A(m,n-1) return A[m,n] 备忘录算法 int ack(inm,int n) { if(a[m][n]) return a[m][n]; if(m==0) return a[0][n]=n+1; if(n==0)return a[m][0]=ack(m-1,1）； return a[m][n]=ack(m-1,ack(m,n-1)); } 动态规划算法实现 用两个一维数组，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]=-1(i0)。 1当m=0时，A(m，n)=n+1。 任给一个t，当ind[0]=t时，能够求出val[0]的值，val[0]等于ind[0]+1。 2当n=0，m0时，A(m，n)=A(m-1,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]时，val[i]’=val[i-1]。 关键代码 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) //?只要未达到边界,则继续?while-循环 { val[0]++; //?每循环一次?刷新?val[ ] ind[0]++; //?每循环一次?刷新?ind[ ] for(j=1;j=