c-如何迭代地编写阿克曼函数

Question

我编写了Ackermann函数的递归版本，它运行正常：

int ackermann_r(int m, int n) {
if(m == 0) {
return n + 1;
} else if(n == 0) {
return ackermann_r(m - 1, 1);
} else {
return ackermann_r(m - 1, ackermann_r(m, n - 1));
}
}

然后我尝试迭代地重写代码：

(我不知道如何使用malloc使用2D数组，所以你可能会觉得代码很脏…(

int ackermann_i(int m, int n) {
int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0) {
A[i*(n+1) + j] = j + 1;
} else if(j == 0) {
A[i*(n+1) + j] = A[(i-1)*(n+1) + 1];
} else {
A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]];
}
}
}
return A[m*(n+1) + n];
}

但迭代版本打印了一个错误的答案。例如：

m: 3
n: 2
recursive: 29
iterative: 3

为什么我的迭代代码不起作用？

Answer 1

未定义的行为

不幸的是，由于对未初始化值的访问和越界访问，您的代码显示出未定义的行为。显示这种行为的最简单的测试是m = 1, n = 0。这表明只有外循环的两次迭代和内循环的一次迭代，因此更容易分析：

int ackermann_i(int m, int n) {
int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0) {
A[i*(n+1) + j] = j + 1;              //       (1)
} else if(j == 0) {
A[i*(n+1) + j] = A[(i-1)*(n+1) + 1]; //       (2)
} else {
A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]]; // (3)
}
}
}
return A[m*(n+1) + n];
}

因此，让我们手动迭代：

• i = 0, j = 0。我们输入(1)并设置A[0 + 0] = 1
• i = 1, j = 0。我们输入(2)并设置A[2 + 0] = A[0 + 1]
• 至少有j == 0，所以我们不关心(3)

但问题是：我们从未设置A[0 + 1]。该值可能为零，也可能是其他随机值；随之而来的是不明确的行为。更糟糕的是，我们的A不够大：这里的(m+1)*(n+1)只是2，所以A[2]是一个越界的数组访问。

这表明了两个问题：

• 我们分配的内存不够大，可能永远都不会，因为a(m, a(m-1,n))中的内部项可能会比n大得多

• 如果我们有一个解决方案，我们需要首先处理琐碎的情况，例如

  for(int j = 0; j <= (n+1); ++j) {
  A[0 + j] = j + 1;          // set all A[i,j] where i = 0
  }
  

算法的一个更深层次的问题

然而，还有一个更深层次的问题。您的代码暗示阿克曼函数可以用θ(m*n(来计算。然而，这是不可能的。相反，你至少需要一个堆栈或类似的东西来计算结果。Java中的这个实现提供了一些灵感。