0

フィボナッチ数列では、n 番目のフィボナッチ項が T であると仮定しましょう。F(n)=T. しかし、私は T を入力として取り、それが級数のどの項であるかを意味する n を返すプログラムを書きたいです (T は常にフィボナッチ数になると仮定します)。それを見つける効率的な方法があるかどうかを見つけたいです。 .

4

2 に答える 2

2

簡単な方法は、F(i) == T になるまでフィボナッチ数の生成を開始することです。これは、正しく実装されている場合、O(T) の複雑さを持ちます (読み取り: 再帰的ではありません)。このメソッドを使用すると、T が有効なフィボナッチ数であることを確認することもできます。

T が有効なフィボナッチ数であることが保証されている場合は、次の近似規則を使用できます 。

複雑に見えますが、そうではありません。ポイントは、ある時点から F(i+1)/F(i) の比率が一定値になることです。フィボナッチ数を生成しているのではなく、単に「インデックス」を見つけているだけなので、そのほとんどを削除して、次のことを実現できます。

breakpoint := f(T)
Any f(i) where i > T = f(i-1)*Ratio = f(T) * Ratio^(i-T)

単純に Log(N, R) を取ることで逆を得ることができます。R は Ratio です。初期の数値の不正確さを調整することで、ブレークポイントを選択する必要さえありません (選択した場合: i > 17 で正しいです)。

比率は、およそ 1.618034 です。6765 (= F(20)) の log(1.618034) を取ると、18.3277 の値が得られます。より高いフィボナッチ数でも精度は変わらないため、切り捨てて 2 を足すだけで正確なフィボナッチ「ランク」が得られます (F(1) = F(2) = 1 の場合)。

于 2012-11-19T13:08:49.433 に答える
0

最初のステップは、次のような非再帰的な方法で fib 番号を実装することです。

fib1=0;fib2=1;
for(i=startIndex;i<stopIndex;i++)
{
     if(fib1<fib2)
     {
        fib1+=fib2;
        if(fib1=T) return i;
        if(fib1>T) return -1;
     }
     else
     {
        fib2+=fib1;
        if(fib2=T) return i;
        if(fib2>t) return -1;
     }
}

ここで、startIndex は 3 に設定され、stopIndex は 10000 程度に設定されます。反復を減らすために、シーケンスのさらに下の連続した fib 番号である 2 つのシード番号を選択することもできます。次に、startIndex を次のインデックスに設定し、stopIndex を適切に調整して計算を行います。実行時間を最小限に抑えるために、マシンのパフォーマンスと予想される最大入力に応じて、シーケンスをいくつかのセクションに分割することをお勧めします。

于 2012-12-03T22:05:17.567 に答える