-3

与えられた数Nがフィボナッチ数であるかどうかをどのように判断できますか？その数がフィボナッチ数でない場合、どのようにして*より小さい最大のフィボナッチ数を決定できNますか？

制限付きの一連のフィボナッチ数を生成することで解決策を見つけましたN。

Pythonでこれを行うためのより良い方法はありますか？

みんなが賛成票を投じている間、私はここで提供される解決策を受け入れました。私は必要なものを投稿し、皆さんから解決策を得たので、それは価値があるとは思いません。

ありがとうございました。

4

2 に答える 2

3

ある整数がフィボナッチ数であるかどうかの簡単なテストNは次のとおりです。

N is a Fibonacci number iff either (5 * n^2 + 4) or (5 * n^2 - 4) is a square number.

独創的な証拠（417ページ）については、こちらをご覧ください：http ://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf

それがフィボナッチ数ではないことが判明した場合N、最も簡単な方法は、1つが見つかるまで小さい数を試し続けることですが、大きい場合は非常に長い時間がかかる可能性がありますN。

于 2012-08-09T08:02:56.980 に答える
1

一般的なアルゴリズムは次のとおりです。単純な方法は再帰で解決することですが、実行時の複雑さの観点からは、まったく役に立ちません。新しい配列を作成します。それをFibArrと呼びましょう。配列に1,1を挿入します。次に、配列のi番目のインデックスの値はfibArr [i-1] + fibArr [i-2]（i> = 3）です。すべての反復で、新しい値がfibArr==Nに挿入されているかどうかを確認します。trueの場合、戻ります。それ以外の場合は、挿入された値がNより大きいかどうかを確認します。trueの場合、fibArrにk個の値があると仮定して、（k-1）値を返します。それ以外の場合は、繰り返し続けます:)

* Pythonを使用すると、さらに簡単に実行できますが、Pythonには配列はなく、リストがあることに注意してください。Javaのようにリストの長さを設定する必要がないため、Pythonの方が簡単です。

于 2012-08-09T07:56:39.797 に答える