4

Javaで再帰的なアッカーマン関数を書いてみました。しかし、私はどこかで非常に間違っていると思います！誰かが私のコードを修正する正しい方向を見て、確認し、多分私を指し示すことができますか？ありがとう！

アッカーマン

私がコードに関して抱えている問題は、私がそれを書いた後、n==0とm==0の場合、これのための領域がないのではないかと思ったということです。これはif（m == 0）に該当しますか、それとも独自のifステートメントが必要ですか？

私の次の解決策は正しいですか？異なる順序で同じ番号を付けると、異なる結果が得られ、これが当てはまるかどうかはわかりません。

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else {

            return 0;

        }

    }

私はそれについてもう少し考えました、そして私は私がさらに間違って行ったと思います。私が何をしたかわからない場合は、それぞれのifステートメントを反対に指定しました。これは、m値とn値が異なる方法で指定されている場合、次のコードが機能すると考えたためです。明らかにそうではありませんが、誰かが私がどこで間違っているのかを説明しようとすることができますか？

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if (n == 0) {

            return m + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((n > 0) && (m == 0)) {

            return ackermann(n-1, m);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else if ((n > 0) && (m > 0)) {

            return ackermann(n-1, ackermann(n, m-1));

        } else {

            return 0;

        }

    }
4

5 に答える 5

5

この部分は間違っています:

    } else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);

それはA(m - 1, 1) でなければなりません

于 2012-01-01T16:19:08.660 に答える
5

最初のバージョンはほぼ正しいと思います。少し変更します：

public static int ackermann(int m, int n) {
    if (m < 0 || n < 0) {
        throw new IllegalArgumentException("Non-negative args only!");
    }

    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermann(m-1, 1); // Corrected!
    } else {
        // perforce (m > 0) && (n > 0)
        return ackermann(m-1, ackermann(m,n-1));
    }
}

ケースはm == 0 && n == 0ケースに含まれている必要がありますm == 0。

編集:アッカーマン関数は、負でない引数に対してのみ定義されていることに注意してください。特に、ackermann(0, -1)例外をスローする必要があります。elseしたがって、最後の句を単に に変換することはできませんthrow。

于 2012-01-01T16:21:16.773 に答える
1

「m = 0 の場合」ルールは n のすべての値に適用されるため、A(0, 0) は 1 です。

'else' 句は、m と n が両方とも関数へのエントリで負の場合にのみ使用でき、これは例外として診断される可能性がありました。実際、m または n のいずれかが負の場合は、エラーを診断する必要があります。別の方法として、A(m, n) はゼロを返さないため、0 はエラーを通知するものと見なすことができます。

A(m, n) を評価するために必要なスタックの深さは、答えと同じであり、A(m, n) は非常に急速に大きくなることに注意してください。わざわざ A(4, 4) を評価しようとしないでください。お使いのコンピュータには十分なメモリがありません。

于 2012-01-01T16:18:32.920 に答える
0

最初のスニペットは問題ありませんが、2 番目のケースではackermann(m-1, n)返されません。ackermann(m-1, 1)発生してはならないデフォルトのケースは、IllegalStateException実際に発生した場合にスローする必要があります。

于 2012-01-01T16:20:51.830 に答える