2

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

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

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

4

1 回答 1

4

未定义的行为

不幸的是，由于访问未初始化的值和越界访问，您的代码会显示未定义的行为。显示此行为的最简单测试是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是，our 不够大：(m+1)*(n+1)只2在这里，所以A[2]是越界数组访问。

这表明两个问题：

  • 我们分配的内存不够大，而且可能永远不会，因为 in 的内部项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) 中计算 Ackermann 函数。然而那是不可能的。相反，您至少需要一个堆栈或类似的可以增长大小的东西来计算结果。Java 中的这个实现提供了一些灵感。

于 2020-03-05T06:48:13.790 回答