5

ユーザーが入力した 2 つの負でない整数のアッカーマン値を計算するプログラムを C で作成しました。プログラムは整数が負でないかどうかをチェックし、負でない場合はそれらのアッカーマン値を計算し、新しい入力または終了を要求します。プログラムは C で正常に動作し、問題はありません。これが私のコードです：

int ackermann(int m, int n){
        if (m == 0) return n + 1;
        if (n == 0) return ackermann(m - 1, 1);
        return ackermann(m - 1, ackermann(m, n - 1));
}

しかし、実際には、大学の授業のニーズのために、MIPS アセンブリ言語の構文と規則をシミュレートする C の修正バージョン (基本的には同じですが、いくつかの異なる構文規則を使用) を使用しています。より具体的には、レジスタを使用して、配列と構造体以外のすべてのデータを操作します。また、for、while、または do-while ループは使用できず、ifおよびgotoを使用します。代わりにステートメント。そこで、この言語で次のプログラムを作成しました (構文が異なる C に過ぎないと言ったように)。私の問題は、(x,0) および (0,y) ユーザー入力 (x および y は非負の数) に対してのみ機能することです。(4,1)、(3,2)、および一般的にゼロを持たないすべての入力では機能しません。これらの計算の膨大なスタックのために、(10,10) のような非常に大きな数では効率的に機能しないことを理解しています。しかし、Ackermann(3,1) == 13 のようないくつかの単純な入力に対して機能するようにしたいと考えてい ます。

//Registers --- The basic difference from C is that we use registers to manipulate data
int R0=0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12,R13,R14,R15,R16,R17,R18,R19,R20,R21,
R22,R23,R24,R25,R26,R27,R28,R29,R30,R31;

int ackermann(int m, int n){

    R4 = m;
    R5 = n;

    if(R4 != 0)
        goto outer_else;
    R6 = R5 + 1;
    return R6;

    outer_else:
        if(R5 != 0)
            goto inner_else;
        R7 = R4 - 1;
        R6 = ackermann(R7, 1);
        return R6;

        inner_else:
            R8 = R5 - 1;
            R9 = ackermann(R4, R8);
            R10 = R4 - 1;
            R6 = ackermann(R10, R9);
            return R6;
}
4

1 に答える 1

6

あなたの問題は、これらのレジスタ値がグローバル変数として定義されており、への内部呼び出しによって更新されているのackermann()に対し、外部呼び出しはそれらの値が変化しないことに依存していることだと思います。たとえば、inner_elseのレジスタ バージョンの句を見てみましょうackermann()。それは を呼び出しackermann(R4, R8)、次のステートメントでは R4 の現在の値に依存しますが、再帰呼び出しは代入ステートメントに到達する前に R4 の設定を変更します。

2 つの一般的な解決策:

  1. レジスタをローカル変数として定義し、コンパイラが関数ごとの呼び出し状態を追跡できるようにします。

  2. 関数の開始時にackermann()、すべてのレジスタの状態を手動で保存し、終了時に同じ状態を復元します。

解決策 1 の方が簡単ですが、教師は解決策 2 を好むのではないかと思います。これは、生成されたアセンブリ コードで実際のレジスタ管理を処理するためにコンパイラが使用する手法を示しているからです。

于 2012-12-07T15:44:12.247 に答える