-1

私は今夜​​いくつかのコードで遊んでいて、フィボナッチ再帰と大きな数のための非常に良い解決策だと思う非常に単純なアルゴリズムをコーディングしました。皆さんがそれについてどう思うか知りたいのですが、より良いものにするための貢献があれば、私たちと共有してください.以下のコードを見てください.

public class RecursiveFibonacci {

    public void calculateFib(long first, long next, long counter, int n) {
        if(counter == n) {
            return;
        }
        counter++;
        if(first == 0 && next == 0) {
            System.out.println("0");
            calculateFib(0, 1, counter, n);
            return;
        }

        if(first == 0 && next == 1) {
            System.out.println("1");
            calculateFib(1, 0, counter, n);
            return;
        }

        if(first == 1 && next == 0) {
            System.out.println("1");
            calculateFib(1, 1, counter, n);
            return;
        }

        long result = first + next;
        if(result > 1) {
            System.out.println(result);
                calculateFib(next, result, counter, n);
        }
    }

    public RecursiveFibonacci() {
        calculateFib(0, 0, 0, 9999999);
    }

    public static void main(String[] args) {
        new RecursiveFibonacci(); 
    }

}
4

5 に答える 5

1

フィボナッチ数列は前の 2 つの値にのみ依存しF(0) = 1ます。これらを覚えて計算すればいいだけです。再帰は、フィボナッチ数を解決する方法としては不十分です。値が高いほど、不必要に多くの呼び出しを行うからです。すぐにスタック領域が不足します。F(1) = 1F(n) = F(n - 1) + F(n - 2)

于 2013-02-12T01:24:12.133 に答える
1

i 番目のフィボナッチを計算する最良の方法は、再帰ではありません。次の式を使用できます。

ここに画像の説明を入力

ここに画像の説明を入力

ここに画像の説明を入力

ファイは黄金比です。ただし、フィボナッチ数の問題は、使用する方法ではなく、数値の桁数に関係しています。数が多いと書きにくくなります。

于 2013-02-12T02:25:04.867 に答える
1

再帰的なフィボナッチも計算の複雑さが非常に高く、おそらく O(n!) であると思いますが、反復は O(n) です :)

于 2013-02-12T01:44:26.983 に答える
0

1 つの問題は、calculateFib()計算結果が返されないことです。結果のみを出力します。そのため、結果を返すようにコードを変更してください。

それが機能したら、実際にはより適している非再帰的なバリアントも試してください。

于 2013-02-12T01:30:15.770 に答える
0

F 9999999には ~2089876 桁があるため、近似値を使用する必要があります。メモ化も検討してください。

于 2013-02-12T01:32:23.447 に答える