0

両方のアルゴリズムが正しく機能しています。2 つのアルゴリズムはフィボナッチ アルゴリズムであり、ユーザーが指定した n でフィボナッチ数を見つけます。3 つのメソッドがあります。そのうちの 2 つは n でフィボナッチ数を返し、最後のメソッドはすべてのフィボナッチ数を表形式で表示しながら両方のメソッドを実行します。列はコードで ADDITION が実行された回数に対応します。

各アルゴリズムでそれぞれ追加された行を表すグローバル カウンター recAdd と itAdd を宣言しました。これらの値は、テスト ハーネスを実行するたびにリセットされますが、ここでは示しません。

public static long recFib(int n){ //Recursive Fibonacci Algorithm
    if( n <= 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }
    else if(n == 2){
        return 1;
    }
    else{
        recAdd++;                               //Counts number of lines added.
        return recFib(n-1) + recFib(n-2);   //Recurisvely adds fibonnachi numbers. Starts with user's input n. Method is called repeatedly until n is less than 2.
    }
}

public static long itFib(int n){ //Iterative Fibonacci Algorithm
    long x, y, z;

    if(n == 0){
        return 0;
    }
    else{
        x = 1;
        y = 1;

        for(int i = 3; i <=n; i++){
            z = x+y;        //z is equal to the addition of x and y, which serve as f(n-1) + f(n-2).
            x = y;      //x is shifted to the next fibonacci number, previously known as y.
            y = z;      //y is set equal to z, which was the new value created by the old y and the old x.
            itAdd++;        //counts how many times addition has occured.
        }
    }
    return y;
}   

public static void doTheyMatch(int n){

    System.out.printf("%s %15s %15s %15s %15s", "i", "Recursive", "recAddCount", "Iterative", "itAddCount\n\n"); //Tab header

    for(int i = 0; i <= n; i++){
    System.out.printf("%d %12d %12d %12d %12d\n", i, recFib(i), recAdd, itFib(i), itAdd);       
    }

    System.out.printf("%s %15s %15s %15s %15s", "\ni", "Recursive", "recAddCount", "Iterative", "itAddCount\n"); //Repeat for quick referencing
}

出力はこちらです (これらのテキスト ボックスに出力を投稿する際に問題があります =/): http://i.imgur.com/HGlcZSn.png

「doTheyMatch()」メソッド中に加算カウンターが大きくずれているのは、このメソッドを実行するループのためであると確信しています。(メソッドは n 回ループし、ループしている間、反復メソッドと再帰メソッドは独自のメソッド内で反復します)。追加された行数を数える別の方法がわかりません。何かアドバイス？

ありがとう！

4

4 に答える 4

1

これは、doTheyMatch 関数で加算カウンターをリセットしなかったためです。

次のようなことをする必要がありました：

System.out.printf("%d %12d %12d %12d %12d\n", i, recFib(i), recAdd, itFib(i), itAdd);

// reset counters
recAdd = 0;
itAdd = 0;
于 2013-03-28T05:15:01.940 に答える
0

ここで何をしようとしているかの問題は、関数を再帰的に呼び出す場合、数値が大きいほど、関数が呼び出される回数が増えることです。数値が 0 または 1 である可能性はそれぞれ 1 であるため、関数はその回数だけ呼び出されます。あなたがする必要があるのは、recAdd++;これらの if ブロック内にステートメントを入れることです:

if( n <= 0){
    return 0;
}
if(n == 1){
    return 1;
}
else if(n == 2){
    return 1;
}
于 2013-03-28T05:16:51.453 に答える
0

再帰では、メソッドが分岐を呼び出し、再帰プロセス中にメソッドを複数回呼び出すためです。これは、反復よりも速い速度で合計されることを意味します。紙の上で小さい数のメソッド呼び出しをいくつかマッピングしてみて、itAdd 変数と recAdd 変数を追跡すると、私の言いたいことがわかるでしょう。お役に立てれば。

于 2013-03-28T05:17:22.980 に答える
0

これが役に立つかどうかはわかりませんが、特定の数のフィボナッチを見つけようとしている場合は、 が反復回数またはシーケンス内の特定の数である式をn使用できます。F(n) = (k^n-p^n)/sqrt(5)nk = (1+sqrt(5))/2p = (1-sqrt(5))/2

于 2013-03-28T05:39:50.500 に答える