制限付きフィボナッチ数列

Question

<p><code>N</code> から <code>N K</code> までのフィボナッチ数列を生成し、<code>array[K]< /code> を返す関数を実装したいと考えています; 要素のうち、(0<=N<=370; 0<=N K<=371; 0<=K<=255)。 入力が n:370, k:1 の場合、最後の試行である n2 は必要性と範囲を超えていました。コードを簡素化し、複数の <code>if</code> ステートメントを使用しないようにしたいと考えています。ありがとう。 </p><p><strong>更新: </strong></p><p>これはブロックチェーンのスマートコントラクトであり、<code>int</code> は 256 ビットです<code>N K >= 369</code> の場合、<code>n2</code> の最後のループはオーバーフローします。 </p> <pre class="brush:js;toolbar:false;">function getFibSeq(n, k) { 数値 = []; とします。 n1 = 0 とします。 n2 = 1 とします。 i = 0 とします。 j = (n k) とします。 while (i < j){ if((i - n) >= 0){ 出力.push(n1); } if((j - i - 1) > 0){ 温度 = n1 とします。 n1 = n2; if((j - i - 2) > 0) { n2 = 温度 n2; } } i = i 1; } 出力を返します。 } </pre> <p><br /></p>

Answer 1

ビネの公式と呼ばれる、n 番目のフィボナッチ数を計算するための閉じた公式があります。これにより、O(1) の漸近時間計算量における n 番目の数値を取得できます。

これは、任意の n のフィボナッチ数を計算する方法を示す例です。

これを拡張して、特定の問題を解決します。 n-1 と n の値を計算することをお勧めします。次に、目的の値を取得するために k 回繰り返します。繰り返しながら結果を追跡すれば問題はないはずです。

リーリー

注: この式は、小さな n 値に対しては正確な結果を返しますが、JavaScript の浮動小数点演算の制限により、大きな値に対しては精度が失われる可能性があります。