Как переписать функцию Аккермана в нерекурсивном стиле?

Ответ 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;
}

Ответ 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

При этом вы можете найти нерекурсивное отношение (определение нерекурсивной функции), которое вы можете использовать.

Изменить: похоже, что это функция Ackermann, полная вычислимая функция, которая не примитивно-рекурсивная.

Ответ 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;
}

Ответ 4

Все ответы, опубликованные ранее, не соответствуют 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

Ответ 5

Мне не удалось получить ответ @LightyearBuzz, но я нашел этот код Java 5 из WikiWikiWeb, который работал для меня:

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

Ответ 6

Написано на 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