c++ - C ++でフィボナッチ数列をすばやく解くにはどうすればよいですか?

Question

N 番目のフィボナッチ数を N とすると、ある整数が N 時間以内にフィボナッチ数であるかどうかを判断することは可能ですか? 私はソリューションを最適化しようとしていますが、これは非常に役立ちます。

私はすべての外部ライブラリも除外しようとしています (そのため、以下の回答の Math.sqrt() のようなものは私の目的では機能しません)。他の提案は素晴らしいでしょう。

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

Answer 1

おそらく、このプロパティを使用できます。

5 N^2 + 4N は、またはが平方数である場合に限り、フィボナッチ数です5N^2 – 4。

正方形の問題の効率的な解決策については、この投稿をご覧ください。

お役に立てれば

Answer 2

フィボナッチ数をある程度まで事前に計算しておくと、線形検索を使用するよりも効率的にリストで自分の数を検索できる場合があります。

フィボナッチ数は急速に増加するため、それらを保存することが問題になるとは思えません。つまり、最初の100程度を保存する場合は、3.5e+20までのすべての数値をカバーします。

最初のMフィボナッチ数を保存するとします。次に、二分探索を使用する最悪のケースはlog(M)です。M与えられたフィボナッチ数を計算するための公式がありますM; これを使用して、両方MのMフィボナッチ数を概算し、数（NリストサイズではなくM）の観点から境界を取得できます。これで最終的にはのようなものになると思いますlog(log(N))が、確認してください。