问题标签 [ackermann]

我正在努力学习更多关于 Ackermann 的函数、递归时间和一般函数学的信息，但是，我的代码无法编译。我觉得这与 中的数组有关acktgen()，但我不是 100% 确定。

我知道这不是最有效的阿克曼算法，但我只是以它为例。

编译器错误：

我尝试编写此代码来计算 Ackerman 值以及调用该函数的次数。但是，计数器一直停留在 0。你能帮帮我吗？

可能不需要太多解释这是什么，它甚至完全按照我想要的方式工作。我真正的问题是程序终止。我已经输出跟踪了我的返回值和我在我的主函数中使用的嵌套 for 循环来单步执行值。我看不出发生这种情况的原因，但是在最后一次通过我的循环后，程序需要多花 10 分钟才能真正终止。尽管我的循环索引正在增加（因为预检查），但我的 Ackermann 函数显然没有执行额外的迭代（无论如何我都不想这样做）。另一方面，唯一合乎逻辑的解释是循环没有中断，但如果是这种情况，我的 Ackermann 函数应该返回一个新的 b 值。所以我能想到的唯一其他原因是它 s 需要很长时间的垃圾收集来清除我的数据结构并刷新内存堆。对于那些不熟悉的人，这里的想法是将传统上呈现为超级繁琐的递归函数的东西实现为迭代函数。递归：

给定正整数 m 和 n：如果 m = 0，则返回 n + 1；否则，如果 n = 0，则返回 Ackermann(m - 1, 1); 否则返回 Ackermann(m - 1, Ackermann(m, n - 1))。所以迭代地，这个想法是使用堆栈来模拟递归函数调用，这样您就可以使用堆中的内存并且您不依赖于调用堆栈大小，这会限制您的执行时间。我担心我忽略了我的流程中的某些东西，这会导致计算完成时间和我的程序到达用户干净退出的时间之间的这些长时间延迟。

这是我的代码：

想法？旁注，这是 c#，但这种行为也发生在使用 MinGW 编译的 C++ 中。

我用 C 编写了以下代码。我们可以称它为尾递归实现吗？

如果它不是尾递归的，请建议如何做到这一点。在 C/C++/Java 或非函数式编程语言中，任何对 Ackermann 尾递归版本的引用都会很好。

我试图理解 OCaml 中的 Y 组合子。我从这里拿了一些代码，并试图用它来编写 Ackermann 函数。在链接中的示例中，函数只需要一个参数。Ackermann 函数需要两个参数，因此我一直遇到语法错误。我到目前为止的代码是

我需要做什么才能让它工作？谢谢。

我找到了 Ackermann 函数的这个版本，并尝试在 MIT Scheme Lisp 中对其进行编码，但没有成功：

阿克曼函数 A(m,n)

当 m=0 时

A(m,n)=n+1

当 m>0 且 n=0 时

A(m,n)=A(m-1,1)

当 m>0 且 n>0 时

A(m,n)=A(m-1,A(m,n-1))

（在这里找到http://www.gfredericks.com/sandbox/arith/ackermann）

我的方案代码：

现在一些结果：

(acker2 0 0) 值：1

(acker2 0 1) 值：2

(acker2 0 2) 值：3

(acker2 2 2) 对象 2 不适用

(acker2 1 23) 对象 1 不适用

(acker2 8 0) 对象 7 不适用

解决方案是什么？

我目前正在做一个阿克曼函数问题，我们必须为用户输入编写一个故障安全代码。因此，如果通常会使程序崩溃的用户输入，它只会发送一条消息。我能够找出整数值是否太大的异常，但我不知道如何检查用户输入是否为整数。我尝试使用“InputMismatchException”捕获块，但代码开始混乱和出错，或者只是不起作用。

}

我的老师要求我编辑此图形代码。图已经制作好了。他想让我做的是调整代码，以便绘制递归阿克曼值。所以如果把 m = 3 和 n = 2 它画出来。如何调整我的阿克曼方法？有什么建议么？

在算法分析类中，我们看到了 Kruskal 算法的伪代码：

然后，对于不相交的森林，他陈述了以下内容：

在最坏情况时间O(m α (n))。

用于计算步骤 2 和步骤 5-8 的复杂度

对于连接的 G：|E| ≥ |V| -1; m = O(V + E)，n = O(V)；

所以步骤 2、5-8：O((V + E) α(V)) = O(E α(V))

α(V) = O(lg V) = O(lg E)；所以我们得到 O(E lg E) ----- // 这里的 α(V) 怎么相等？

Kruskal：第 3、5-8 步和第 4 步：O(E lg E)

观察：|E| < |V|2 -> lg E = O(lg V)

所以，克鲁斯卡尔复杂度：O(E lg V)

我试图理解这个“alpha(n)”/“α(n)”函数背后的逻辑，从我所读到的内容来看，简单地说，Ackermann 函数是一个以令人难以置信的速度增长的函数，并且inverse 是一种以对数方式缓慢增长的方法。

如果我的解释是正确的，“α(n)”代表什么？这是否意味着 MAKE-SET 操作最多为 O(lg n)？如何/为什么需要使用逆阿克曼？我的印象是这个操作执行了 V 次（对于每个顶点）。在此之后，α(V) 也被简化为 O(lg V) = O(lg E)，这是否意味着，α(V) 最多可以表示为 O(lg V)？

另外，为什么|E| < |V|^2 -> lg E = O(lg V)语句，怎么知道 |E| < |V|^2?

我认为我的问题真的归结为，为什么当我的讲师说它们都是 O(E log V) 时，不相交集的“森林”表示似乎比使用链表实现的那些更有效？因此，与森林实施不相交集的难度增加有什么意义吗？

我在 youtube 上观看此视频 - https://youtu.be/i7sm9dzFtEI ，并决定在 C# 中复制该函数会很有趣

好吧，我运行了它，它在 21 次调用和大约一秒钟后停止了。视频中这家伙的程序显然已经运行了大约 4 周，并且仍在运行。

有什么办法可以让我跑得更久吗？

编辑：我从“调试”更改为“发布”并进行了一次迭代和几秒钟。