algorithm - 初期値が異なるTribonacciシリーズ

Question

初期値が1、2 3、つまりT（1）= 1、T（2）= 2、T（3）= 3などの任意の数である場合に、行列乗算法を使用してn番目のトリボナッチ数を見つける方法。

T（n）= T（n-1）+ T（n-2）+ T（n-3）の場合、nが非常に大きい場合のT（n）の見つけ方、行列で説明していただければ幸いです。乗算法。初期行列の作成方法。

Answer 1

行列の乗算方法では、行列の漸化式を使用します。

フィボナッチ数列の場合、隣接するフィボナッチ数を表す長さ2のベクトルを定義できます。このベクトルを使用して、行列の乗算で漸化式を定義できます。

同様に、Tribonacci系列の漸化式は次のように記述できます。

唯一の違いは、ベクトルと行列のサイズが異なることです。

ここで、大きなTribonacci数を計算するには、行列の乗算をn回適用するだけで、次のようになります。

べき乗アルゴリズムを使用できるため、n（M ⁿ ）の累乗の行列を効率的に計算できます。

スカラーの多くの効率的なべき乗アルゴリズムは、ウィキペディアの「二乗によるべき乗」で説明されています。行列指数にも同じ考え方を使用できます。

これを行う簡単な方法を説明します。まずn、2進数として記述します。例：

n = 37 = 100101

次に、前の2の累乗を2乗して、Mを2の各累乗に計算します。M1 ^、 M ² = M ¹ M ¹、M ⁴ = M ² M ²、M ⁸ = M ⁴ M ⁴、M ¹⁶ = M ⁸ M ⁸、M ³² = M ¹⁶ M ¹⁶、..。

そして最後に、の2進数に対応するMの累乗を乗算しnます。この場合、M ⁿ = M ¹ M ^4M32です。

それを計算した後、最初の3つの値、つまり、行列にTribonacciベクトルを掛けることができます。

行列のサイズは固定されているため、各行列の乗算には一定の時間がかかります。O(log n)行列の乗算を行う必要があります。^{したがって、時間内にn番目}のTribonacci数を計算できますO(log n)。

O(n)これを、n^番目のTribonacci番号（つまり）までの各Tribonacci番号を計算することにより、時間がかかる通常の動的計画法と比較しfor (i = 3 to n) {T[i] = T[i-1]+T[i-2]+T[i-3];} return T[n];ます。

---

選択した言語で行列の乗算をコーディングする方法を知っていると仮定します。

Answer 2

検討：

                           | a1 b1 c1 |
[f(n) f(n - 1) f(n - 2)] * | a2 b2 c2 | = [f(n + 1) f(n) f(n - 1)]
                           | a3 b3 c3 |

それに基づいてマトリックス内の未知数を見つけてください。それが必要なマトリックスになります。

この場合の答えは次のとおりです。

1 1 0
1 0 1
1 0 0

この方法は一般的ですが、k前の項を合計しても、前に定数がある場合などでも機能します。