1

很明显我不是一个称职的 C 作家，但想知道，关于这个问题，阿克曼在 Haskell/GHC 方面效率很低（这可能让我不合理地感到恼火）为什么作者的程序来计算威廉·阿克曼的著名函数：

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

int main() {
  printf("%d\n", ack(4,1));
  return 0;
}

工作正常，但是当给出一个明显的优化（这在其他地方有帮助）并给出论点（4,2）——这在算法上当然是残酷的——结束时Segmentation fault: 11：

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

int main() {
  printf("%d\n", ack(4,2));
  return 0;
}

如果我注释掉“优化”行if (m == 1) return n+2;，程序会像在其他语言中一样继续运行，但不会产生相同的效果——至少在运行 5 分钟后不会。[更正，似乎确实如此——在 8 分 41 秒之后]（我应该注意，我使用的是 os x 附带的 gcc，但似乎也发生了同样的情况，例如gcc-4.7.2on ideone.com。）

我同意该程序甚至不值得被编译，但想知道为什么分段错误（通常被视为恐怖并且在我熟悉的其他语言中被视为语言缺陷或编译器错误）是对gcc.

4

1 回答 1

5

这两个程序都用完了堆栈，而您的改进做得更快。请注意，所需的堆栈与参数“n”成正比，并且“n”增长很快。所以没有错误，只是一台有限的机器。

让我从我的存档中添加一些代码，只是为了好玩和更快。它还显示了“n”随着“m”的每个增量而增长的速度。

typedef unsigned long long N;
N acker (N m, N n)
{
        while (1)
        switch (m)
        {
        case 0: return n+1U;
        case 1: return n+2U;
        case 2: return 2U*(n+1U)+1U;
        case 3: return (1LLU<<(n+3U))-3U;
        default:
                if (n == 0U)
                        n = 1U;
                else
                        n = acker(m, n-1U);
                m--;
                break;
        }
        return n+1U;
}
于 2013-04-24T00:16:10.880 回答