Question

我有功能

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?

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

先前公布的所有答案都无法正确执行阿克曼。

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

Answer 3

这看起来像家庭作业,所以我不会给你答案但我会引导你走正确的方向:

如果您想要解析循环, 您可能有必要列出所有正在进步的值, 让 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

这样,您就可以找到一种非递归性的关系(一种非递归性功能定义),您可以使用这种关系。

编辑 : 因此它看起来像 < a href=" "http:// demonstrations. wolfram.com/ recursion In TheAckermannFunction/" rel="no follow" > Ackermann 函数 , 是一个总可计算函数, 是 < 坚固 > 不 < / 坚固 > 原始递归性。

Answer 4

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

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 5

我无法得到@LightyyearBuzs对工作的回复, 但我发现这个Java 5代码来自

Answer 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

Answer 7

Well I came here to find the answer of this question. But could not write a code even after looking at the answers. So, I tried it myself and after some struggle built the code. So, I will give you a hint (because I feel etiquettes here are that the homework questions are not meant to be fully answered). So you can use a single stack to compute the function without using recursion. Just look at the flow of control in David s answer. You have to use that. Just start a while(1) loop and inside that check for the case your arguments are satisfying. Let the desired block amongst if-else blocks execute.Then push the two latest arguments of ackerman function into the stack. Then at the end of the loop pop them and let the cycle repeat till an end condition is reached where no further arguments of ackermann function are generated. You have to put a for statement inside the while loop to keep checking it. And finally get the final results. I don t know how much of this is understandable, but I wish I could have some idea to start with. So, just shared the way.

Answer 8

使用 C+++ 编写。 Stackack 只存储 m 值, 对所有输入都工作正常

int ackermann(int m, int n) {
    stack<int> s;
    s.push(m);
    while(!s.empty()) {
        m = s.top();
        s.pop();
        if(m == 0) {
            n++;
        }
        else if(n == 0) {
            s.push(--m);
            n = 1;
        }
        else {
            s.push(m-1);
            s.push(m);
            n--;
        }
    }
    return n;
}

友情链接