我有功能
public static int func(int M,int N){
if(M == 0 || N == 0) return M+N+1;
return func(M-1, func(M, N-1));
}
如何以非递归风格重写它？也许，它是实现某种算法吗？
问问题
16114 次
7 回答
16
不完全是 O(1)，但绝对是非递归的。
public static int itFunc(int m, int n){
Stack<Integer> s = new Stack<Integer>;
s.add(m);
while(!s.isEmpty()){
m=s.pop();
if(m==0||n==0)
n+=m+1;
else{
s.add(--m);
s.add(++m);
n--;
}
}
return n;
}
于 2012-05-24T20:07:21.197 回答
7
之前发布的所有答案都没有正确实现 Ackermann。
def acker_mstack(m, n)
stack = [m]
until stack.empty?
m = stack.pop
if m.zero?
n += 1
elsif n.zero?
stack << m - 1
n = 1
else
stack << m - 1 << m
n -= 1
end
end
n
end
于 2019-01-24T23:30:50.867 回答
6
这看起来像家庭作业，所以我不会给你答案，但我会引导你朝着正确的方向前进：
如果你想分解递归，列出所有的值可能会很有用，让 m = {0...x} n = {0...y}。
例如：
m = 0, n = 0 = f(0,0) = M+N+1 = 1
m = 1, n = 0 = f(1,0) = M+N+1 = 2
m = 1, n = 1 = f(1,1) = f(0,f(1,0)) = f(0,2) = 3
m = 2, n = 1 = f(2,1) = f(1,f(2,0)) = f(1,3) = f(0,f(1,2)) = f(0,f(0,f(1,1))
= f(0,f(0,3)) = f(0,4) = 5
有了这个，你可以想出一个你可以使用的非递归关系（一个非递归函数定义）。
编辑：所以看起来这是Ackermann function，一个非原始递归的总可计算函数。
于 2012-05-24T17:29:53.783 回答
2
这是我自己已经检查过的正确版本。
public static int Ackermann(int m, int n){
Stack<Integer> s = new Stack<Integer>;
s.add(m);
while(!s.isEmpty()){
m=s.pop();
if(m==0) { n+=m+1; }
else if(n==0)
{
n += 1;
s.add(--m);
}
else{
s.add(--m);
s.add(++m);
n--;
}
}
return n;
}
于 2017-07-31T10:04:36.893 回答
0
好吧，我来这里是为了找到这个问题的答案。但是即使在查看答案后也无法编写代码。所以，我自己尝试了一下，经过一番努力构建了代码。所以，我会给你一个提示（因为我觉得这里的礼仪是家庭作业问题并不意味着完全回答）。因此，您可以使用单个堆栈来计算函数，而无需使用递归。看看大卫回答中的控制流程。你必须使用它。只需启动一个 while(1) 循环并在其中检查您的参数是否令人满意。让 if-else 块中的所需块执行。然后将 ackerman 函数的两个最新参数压入堆栈。然后在循环结束时弹出它们并让循环重复直到达到结束条件，此时不再生成 ackermann 函数的参数。您必须在 while 循环中放置一个 for 语句才能继续检查它。并最终得到最终结果。我不知道这在多大程度上是可以理解的，但我希望我能有一些想法开始。所以，只是分享了方式。
于 2021-09-19T04:47:06.847 回答
0
用python编写，仅使用1个数组和1个变量，希望对您有所帮助！
def acker(m,n):
right = [m]
result = n
i = 0
while True:
if len(right) == 0:
break
if right[i] > 0 and result > 0:
right.append(right[i])
right[i] -= 1
result -= 1
i += 1
elif right[i] > 0 and result == 0:
right[i] -= 1
result = 1
elif right[i] == 0:
result += 1
right.pop()
i -=1
return result
于 2019-09-05T03:18:16.853 回答
0
我无法得到@LightyearBuzz 的工作答案，但我从WikiWikiWeb中找到了对我有用的 Java 5 代码：
import java.util.HashMap;
import java.util.Stack;
public class Ackerman {
static class Pair <T1,T2>{
T1 x; T2 y;
Pair(T1 x_,T2 y_) {x=x_; y=y_;}
public int hashCode() {return x.hashCode() ^ y.hashCode();}
public boolean equals(Object o_) {Pair o= (Pair) o_; return x.equals(o.x) && y.equals(o.y);}
}
/**
* @param args
*/
public static int ack_iter(int m, int n) {
HashMap<Pair<Integer,Integer>,Integer> solved_set= new HashMap<Pair<Integer,Integer>,Integer>(120000);
Stack<Pair<Integer,Integer>> to_solve= new Stack<Pair<Integer,Integer>>();
to_solve.push(new Pair<Integer,Integer>(m,n));
while (!to_solve.isEmpty()) {
Pair<Integer,Integer> head= to_solve.peek();
if (head.x.equals(0) ) {
solved_set.put(head,head.y + 1);
to_solve.pop();
}
else if (head.y.equals(0)) {
Pair<Integer,Integer> next= new Pair<Integer,Integer> (head.x-1,1);
Integer result= solved_set.get(next);
if(result==null){
to_solve.push(next);
}
else {
solved_set.put(head, result);
to_solve.pop();
}
}
else {
Pair<Integer,Integer> next0= new Pair<Integer,Integer>(head.x, head.y-1);
Integer result0= solved_set.get(next0);
if(result0 == null) {
to_solve.push(next0);
}
else {
Pair<Integer,Integer> next= new Pair<Integer,Integer>(head.x-1,result0);
Integer result= solved_set.get(next);
if (result == null) {
to_solve.push(next);
}
else {
solved_set.put(head,result);
to_solve.pop();
}
}
}
}
System.out.println("hash size: "+solved_set.size());
System.out.println("consumed heap: "+ (Runtime.getRuntime().totalMemory()/(1024*1024)) + "m");
return solved_set.get(new Pair<Integer,Integer>(m,n));
}
}
于 2018-06-29T00:16:47.747 回答