如何重写非递归式的阿克曼的功能？(How to rewrite Ackermann 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));
}

如何重写它的非递归式的？ 也许，是实现某种算法？

Answer 1:

不太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;
}

Answer 2:

这看起来像功课，所以我不会给你答案，但我将带领你在正确的方向：

如果要细分的递归，为你列出所有的值，因为他们的进步，让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

有了这个，你可以拿出一个非递归关系（非递归函数的定义），您可以使用。

编辑：所以看起来这是阿克曼函数 ，共可计算函数不是原始递归。

Answer 3:

这是一个已经被自己检查的一个正确的版本。

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;
}

Answer 4:

我不能让@ LightyearBuzz的答案工作，但我发现从这个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));
  }
}

Answer 5:

所有的答案以前发布的不正确实现阿克曼。

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

文章来源: How to rewrite Ackermann function in non-recursive style?