问关于gcc的阿克曼函数分段
EN

Stack Overflow用户

提问于 2013-04-24 08:08:56

回答 1查看 514关注 0票数 1

很明显，我不是一个称职的C语言作者，但我想知道，关于这个问题Ackermann very inefficient with Haskell/GHC (这个问题可能不合理地激怒了我)，为什么作者的程序要计算Wilhelm Ackermann的著名函数：

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分钟后不会。Correction, it seems it does -- after 8m41s

我同意这个程序甚至不值得编译，但我想知道为什么分段错误，在我熟悉的其他语言中通常被视为语言缺陷或编译器错误，是gcc的适当响应。

gcc

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-04-24 08:16:11

这两个程序都在堆栈之外运行，而您的改进会更快地完成。请注意，所需的堆栈与参数'n‘成正比，'n’增长很快。所以没有bug，只是一台有限的机器。

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

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;
}

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/16181210

复制

相似问题

问关于gcc的阿克曼函数分段
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问关于gcc的阿克曼函数分段EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问关于gcc的阿克曼函数分段
EN