algorithm - 漸化式

Question

非常に大きなn（たとえば10 ^ 14）のトリボナッチ数を最も複雑に計算する方法。Tribonacci番号は、と同様に定義されF(n)=F(n-1)+F(n-2)+F(n-3)ますF0=1, F1=2, F2=4。

F(n)=aF(n-1)+bF(n-2)+cF(n-3)または、と同様に定義された再発 F0=1, F1=2, F2=4。

n番目のフィボナッチ数と同じようにlog（n）のn番目の項を計算したいと思います。

行列指数を使用してn番目の項を計算するための基本行列を生成するにはどうすればよいですか？

以前はDPを使用して実装しようとしていましたが、このような大きなサイズの配列を取得できないため、正常に機能しません。同様に、10 ^ 14の非常に多数のオーダーのスタックオーバーフローが原因で、再帰はここでは機能しませんでした。

score 13 · Accepted Answer

トリボナッチ数の最良の漸近的複雑さは、フィボナッチ数のような行列指数法を使用することです。^{具体的には、正しく記述すると、これはO（n）（動的計画法のように）やO（3 n}）（単純な解のように）ではなく、O（log n）整数演算です。

対象のマトリックスは

    [1, 1, 1]
M = [1, 0, 0]
    [0, 1, 0]

n番目のトリボナッチ番号は^Mnの左上隅にあります。log（n）の複雑さを実現するには、行列指数を2乗して計算する必要があります。

（のF(n+3) = a F(n+2) + b F(n+1) + c F(n)場合、マトリックスは次のとおりです。

    [a, b, c]
M = [1, 0, 0]
    [0, 1, 0]

結果は{Fn _{+ 2}、F _{n + 1}、F _n } = M ⁿ {F ₂、F ₁、F ₀ }です。こちらも参照してください。）

score 7 · Accepted Answer

動的計画法ソリューションは、10^14要素の配列を必要としません。必要なのは3つだけです。

各ステップは前の3つの要素のみを使用しているためF(1000)、の場合、実際には必要ないことに注意してくださいF(5)。

不要になった要素を上書きして、新しい番号と見なすことができます。

%オペレーターはこの目的のためのあなたの友達です。

2 に答える 2