问题标签 [ackermann]

我正在尝试在haskell中编写一个超操作函数。

它通常写成，ackermann(a,b,n)但出于部分应用目的，我认为把它n放在第一位更有意义。因此我称之为hypOp n a b

我发现最自然的形式使用折叠 aoreplicate列表，如下所示：

根据折叠的函数参数，这可以是加法、乘法、取幂、四进制等。

非正式概述：

出于关联的原因，我的印象是我必须使用右折叠，这是不幸的，因为左折叠 ( foldl') 可用的严格性会很有用。

左右折叠问题

当我从一开始就使用后继功能时，我遇到了一个问题。所以我使用 (+) 作为我的基本折叠的函数

前几个n值，“手动”完成：

我尝试通过上述方法进行正式定义：

其他使用递归数组的尝试（没有任何显着差异）：

所以我的问题是...

1. 任何一般性建议，不同的功能方法？我似乎找不到避免溢出的方法，除了使用非常“命令式”的风格，这不是我在使用 haskell 并尝试以惯用风格​​编码时的意图
2. 如何处理我的一对一问题，以便我可以从最底层“正确”开始succ
3. 严格性和左右折叠。有办法进去工作seq吗？我可以使用某种方法来foldl1'代替foldr1并避免上述问题？

我试图在 x86 NASM-Assembly 中实现递归 Ackermann-Peter-Function。函数定义如下：

*a(0;m) = m + 1

*a(n + 1; 0) = a(n; 1)

*a(n + 1;m + 1)) = a(n;a(n + 1;m))

我的问题是我什至无法想象如何正确启动。到目前为止，我只在 Assembly 中递归地实现了“x 的幂”函数。

这是我到目前为止所拥有的：http: //pastebin.com/rsWALyCq（德语提示只要求输入 n 和 m）

我很感谢我能得到的每一点帮助。

--

所以我现在做了 push/pop Statements Symetric，但仍然出现分段错误。我试图调试整个事情，并在第一个案例中放置了一个 Debug-Message。我编译了程序并使用 n=0 和 m=0 进行了尝试，并且没有打印调试消息，所以他甚至没有进入第一种情况。我似乎无法弄清楚为什么他不这样做。

这是我目前的尝试： http: //pastebin.com/D4jg7JGV

谁能给我一个直观的解释为什么阿克曼函数http://en.wikipedia.org/wiki/Ackermann_function与用于不相交集的联合查找算法的摊销复杂性有关http://en.wikipedia.org/ wiki/Disjoint-set_data_structure？

Tarjan 的数据结构书中的分析不是很直观。

我也在Introduction to Algorithms中查到过，但也显得过于严谨和不直观。

谢谢你的帮助！

我正在了解我的系统计算阿克曼算法的两个和三个参数版本的能力。对于非常小的 m 和 n 值，我的系统将计算并打印从 A0 和 A1 方法调用返回的结果。但是任何高于 3 或 4 的东西都不会返回并冻结我正在使用 atm 的终端。我的问题是我确实确定了我的机器可以计算的 m 和 n 的值。

我已经尝试了一些方法来捕获堆栈溢出，因为我所知道的 C++ 没有我可以捕获的 stackoverflowexception。try-catch 块不起作用。在下面的代码中，我使用 getrlimit() 来查找堆栈限制，在主 gStackRef 中创建一个地址位置。我调用 checkStack 递归地检查指向 gStackLimit 的局部变量指针。

有没有更好的方法来检查与递归方法相关的堆栈使用情况？我还要检查段故障吗？我会让你知道我在一个 unix 终端上运行。

我尝试用 Java 编写递归 Ackermann 函数。但我想我在某个地方走错了！任何人都可以看看，检查并指出我纠正代码的正确方向吗？谢谢！

我对代码的问题是，在我写完它之后，我想，如果 n == 0 和 m == 0，没有这个区域怎么办？这会属于 if (m == 0) 还是需要它自己的 if 语句？

我的以下解决方案是否正确？如果我以不同的顺序给它相同的数字，它会给出不同的结果，我不确定这是否是这种情况。

我想了更多，我认为我错得更大。如果你不知道我做了什么，我给了每个 if 语句一个相反的，因为我认为如果 m 和 n 值以不同的方式给出，下面的代码将起作用。显然没有，但有人可以尝试解释我哪里出错了吗？

我正在尝试在 Coq 中定义 Ackermann-Peters 函数，但收到一条我不理解的错误消息。如您所见，我a, b将 Ackermann 的论点打包成一对ab；我提供了一个为参数定义排序函数的排序。然后我使用Function表单来定义 Ackermann 本身，并为它提供参数的排序函数ab。

我得到的是以下错误消息：

错误：没有这样的部分变量或假设：ack。

我不确定是什么困扰了 Coq，但是在搜索互联网时，我发现了一个建议，使用通过排序或度量定义的递归函数可能存在问题，其中递归调用发生在匹配中。但是，使用投影fst和生成不同的错误消息snd。if-then-else有人可以建议如何在 Coq 中定义 Ackermann 吗？

在我的阿克曼函数的家庭工作中，我解决了以下问题

这个函数在 m=3 和 n = 10 的低值下效果很好但是当我给 m = 4/above 或 n = 15/above 时，这不起作用。我没有输出。程序直接退出，没有任何警告、错误或结果。

请一些人告诉我发生这种情况的原因以及我该如何解决这个问题。

我想计算A(3, 20)应该2^23 - 3 = 8388605使用的 Ackermann 函数（参见维基百科）的值Data.MemoCombinators。我的代码是：

但它最终导致堆栈溢出错误;-) 可以调整它还是计算链真的那么长，甚至记忆也无济于事？

任务是创建一个使用递归计算阿克曼方程的程序，我成功地做到了。部分作业说：

“函数应该打印递归函数调用的数量，它是 k 的倍数。对于 n 的值设置 k = 100；m <= 3，并且对于所有其他值设置 k = 1;000;000。您的程序还应该打印进行的函数调用总数。”

ackermann函数应该打印出函数调用和递归函数调用的数量，但我不知道该怎么做。任何帮助都会很棒。谢谢！

这是我到目前为止所拥有的：

在 C 语言中，我已经实现了Ackermann 函数，但现在正试图找到 N 的最大值。例如，如果 m = 1 找到正确计算的 n 的最大值。到目前为止，我一直在使用“猜测和检查”，但似乎必须有更好、更准确的方法。有人可以提供一些指导吗？Ackerman 函数与可以处理多少堆栈有很大关系，所以也许这个问题纯粹是任意的......感谢任何帮助，谢谢！