Ackermann函数定义如下：
1，请采⽤备忘录⽅法设计⼀个求解该函数的递归算法。
2，请⽤动态规划⽅法设计⼀个⾮递归求解算法，该算法由两个嵌套循环组成，只能使⽤O(m)内的空间。
解法⼀：
解法⼆：动态规划⽅法
⽤两个⼀维数组ind[i]和val[i]，使得当ind[i]等于t时，val[i] = A(i, ind[i])。初始时，令ind[0] = 0，val[0] = 1，ind[i] = -1(i > 0)，val[i] = -1(i>0)。
1，当m = 0时，A(m,n) = n+1。任给⼀个t，当ind[0] = t时，能够求出val[0]的值，该值等于ind[0]+1；
2，当n = 0，m > 0时，A(m,n) = A(m-1,1)。能够求出当ind[i] = 0时，val[i]的值，该值等于当ind[i-1]等于
1时val[i-1]的值；
3，当m > 0，n > 0时，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)
{
val[0]++;
ind[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];
}
}
return val[m];
}
Java代码如下：
package ackermann;
public class Ackermann_2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(ack(4,0));
}
public static 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]++;
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];
}
}
return val[m];
}
}
对代码进⾏实例测试结果如下：（与备忘录⽅法的测试实例相同）ack(0,5) = 6 ack(1,5) = 7
ack(2,4) = 11
ack(3,6) = 509
ack(4,0) = 13
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议