1 
1 4 10 22 45 88 167

このシーケンスは、フィボナッチ数とそれ自体の畳み込みです。再発は

a[n] = a[n-1] + a[n-2] + Fibonacci[n+2]

0,1,1,2,3,5 ...フィボナッチ数列が（http://oeis.org/A213587）から始まると仮定した場合

対数時間以上の時間を生成するにはどうすればよいですか？これは宿題でもコンテストの問題でもないことに注意してください。私はフィボナッチ適用シーケンスに取り組んでいます。

4

3 に答える 3

2

これが閉じた式であり、ほぼ保証されていますO(1)（Mathematicaを使って計算されます）

入力：

RSolve[{a[n] == a[n - 2] + a[n - 1] + Fibonacci[n + 2], a[1] == 1, a[2] == 4}, a[n], n]

出力（フルサイズはここをクリック）：

リンク

いくつかの浮動小数点演算を使用する必要がありますが、それでもdoubleデータ型から多くの精度を得ることができます。精度が問題になる場合は、GMPまたはその他の任意精度ライブラリを使用してください。

于 2012-09-03T19:29:16.620 に答える
1

漸化式をフィボナッチ数変換に変換することで、これをlog n時間で解くことができました。結局、漸化式にはリュカ数とフィボナッチ数しか含まれていなかったので、2 * logn.Iで解くことができました。ここで数学記号を書く方法を理解したら、ここに証明全体を書きます。

于 2012-09-10T15:16:16.297 に答える
1

これは質問に対する実際の答えではなく、シーケンス全体を生成するためのアプローチにすぎません。O(n)

O(log(n))n番目の要素だけを計算するための時間計算量を意味する場合、nそれまでのすべてが実際には非常に簡単であるとは限りません。O(1)繰り返し処理すると、適切なメモ化を使用して要素ごとに簡単に実行できます。

私はこれを仮定します：

a[1] = 1, a[2] = 1, fib[1] = 0, fib[2] = 1, fib[3] = 1

次に、繰り返して暗記a[n-1]しa[n-2]、途中で次のようにしますfib[n-1]。fib[n-2]

long an_1 = 1;  // a[2]
long an_2 = 1;  // a[1]
long fib_1 = 2; // fib[4]
long fib_2 = 1; // fib[3]

// Starts with a[3]
while (true)
{
    long fib = fib_1 + fib_2;
    long an = an_1 + an_2 + fib;

    std::cout << an;

    fib_2 = fib_1;
    fib_1 = fib;
    an_2 = an_1;
    an_1 = an;
}

編集：これは償却された複雑さと呼ばれます。n-番目の要素までの計算にこの時点に達するとからO(n)すべての要素が。正式な証明はもう少し複雑ですが、これがアイデアです。1nO(1)

于 2012-09-03T18:41:54.900 に答える