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

Question

我写了一个阿克曼函数的递归版本，它运行正常：

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来使用二维数组，所以你会觉得代码很脏...）

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). That's however impossible. Instead, you need at least a stack or something similar that can grow in size to calculate the result. This implementation in Java中计算，提供了一些启发。

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

How to write Ackermann Function iteratively?

c

algorithm

ackermann

未定义的行为

算法的更深层问题