java 如何以非递归方式重写阿克曼函数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10742322/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to rewrite Ackermann function in non-recursive style?
提问by BILL
I have function
我有功能
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));
}
How to rewrite it in non-recursive style ? Maybe, is it implementation some algorithm?
如何以非递归方式重写它？也许，它是实现某种算法吗？
采纳答案by Lightyear Buzz
Not quite O(1) but definitely non-recursive.
不完全是 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;
}
回答by David B
This looks like homework, so I won't give you the answer but I will lead you in the right direction:
这看起来像家庭作业，所以我不会给你答案，但我会引导你走向正确的方向：
If you want to breakdown the recursion, it might be useful for you to list out all the values as they progress, letting m = {0...x} n = {0...y}.
如果您想分解递归，列出所有进行中的值可能对您有用，让 m = {0...x} n = {0...y}。
For example:
例如：
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
With this, you can come up with a non-recursive relationship (a non-recursive function definition) that you can use.
有了这个，您可以提出可以使用的非递归关系（非递归函数定义）。
Edit: So it looks like this is the Ackermann function, a total computable function that is notprimitive recursive.
编辑：所以看起来这是Ackermann 函数，一个不是原始递归的总可计算函数。
回答by Kache
All the answers posted previously don't properly implement 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
回答by Ray Xie
This is the a correct version which already examined by myself.
这是我自己已经检查过的正确版本。
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;
}
回答by Nick S
I couldn't get @LightyearBuzz's answer to work, but I found this Java 5 code from WikiWikiWebthat worked for me:
我无法得到@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));
}
}
回答by Darwin Harianto
Written in python, using only 1 array and 1 variable, hope this helps!
用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
