问题标签 [ackermann]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 如何优化阿克曼函数？
我需要找到阿克曼函数的优化并解释阿克曼问题本身的问题。但是，我不确定我应该从哪里开始。我知道阿克曼函数的增长速度比任何原始递归函数都快。也许使用 BigInteger 存储结果会有所帮助？或者也许使用记忆？
例如，如果我们知道 A(0,1) = 1+1, A(1,0) = A(0,1), A(1, 1) = A(0,A(1,0)) 我可以根据“n”从那里构建。
这听起来合理还是无法实现？是什么实际问题导致它即使对于少数人也能如此快速地增长？
algorithm - 理解 Grossman 和 Zeitman 的算法
我已经阅读了由 Grossman & Zeitman 发表的论文An intrinsic iterative computing of Ackermann's function，其中他们提出了一种优化 Ackermann 函数的算法。
我们知道 Ackermann 函数在子序列 A(m,n) 中产生结果
m=0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,...
m=1: 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
m=2: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
m=3: 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765 , 65533,...
m=4: 13, 65533,...
据说Next数组是为了跟踪我们在每个子序列中的位置，并且Goal数组是在将刚刚计算的值传输到下一个子序列之前跟踪我们需要到达的位置。它所做的只是将值加 1：
我发现很难理解这两个数组如何指示我们在哪里/在哪里移动？当我们停在 时，我很难确定它的确切含义next[m] = n + 1，为什么特别是这个值？我已经尝试过跟踪算法，但我仍然对它的工作原理感到迷茫。这个算法会算作自下而上的实现吗？
这是一个打印值、当前和两个数组的 java 代码