機能があります
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
これにより、使用できる非再帰的な関係（非再帰的な関数定義）を思い付くことができます。
編集：つまり、これは原始再帰ではない完全に計算可能な関数であるアッカーマン関数のように見えます。
于 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
@LightyearBuzzの答えを機能させることができませんでしたが、WikiWikiWebからこのJava5コードが機能することがわかりました。
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 に答える
0
1つの配列と1つの変数のみを使用して、Pythonで記述されています。これがお役に立てば幸いです！
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
さて、私はこの質問の答えを見つけるためにここに来ました。しかし、答えを見てもコードを書くことができませんでした。それで、私はそれを自分で試し、いくつかの苦労の後にコードを構築しました。それで、私はあなたにヒントを与えます（私はここでのエチケットは宿題の質問が完全に答えられることを意図されていないということであると感じるので）。したがって、単一のスタックを使用して、再帰を使用せずに関数を計算できます。Davidの答えの制御の流れを見てください。あなたはそれを使わなければなりません。while（1）ループを開始し、その中で引数が満たされているかどうかを確認します。if-elseブロックの中から目的のブロックを実行してから、アッカーマン関数の最新の2つの引数をスタックにプッシュします。次に、ループの最後でそれらをポップし、アッカーマン関数の引数がそれ以上生成されない終了条件に達するまでサイクルを繰り返します。チェックを続けるには、whileループ内にforステートメントを配置する必要があります。そして最後に最終結果を取得します。これがどれだけ理解できるかはわかりませんが、最初に何かアイデアがあればいいのにと思います。だから、ただ道を共有しました。
于 2021-09-19T04:47:06.847 に答える