具有不同初始值的Tribonacci系列 [英] Tribonacci series with different initial values

问题描述

如果初始值是任意数字，例如1、2 3，即T(1)= 1，T(2)= 2和T(3)= 3，如何用矩阵乘法找到第n个三bonacci数.

How to find nth tribonacci number with matrix multiplication method if the initial values are some arbitrary numbers say 1, 2 3 i.e T(1) = 1, T(2) =2 and T(3) = 3.

如果T(n)= T(n-1)+ T(n-2)+ T(n-3)，那么如果n非常大，如何找到T(n)，如果有人可以，我将不胜感激用矩阵乘法的方法来解释.如何构造初始矩阵.

If T(n) = T(n-1) + T(n-2) + T(n-3) then how to find T(n) if n is very very large, I would appreciate if anyone can explain with matrix multiplication method. How to construct initial matrix.

推荐答案

矩阵乘法方法涉及使用矩阵递归关系.

The matrix multiplication method involves using the matrix recurrence relation.

对于斐波那契数列，我们可以定义一个长度为2的矢量来表示相邻的斐波那契数.使用此向量，我们可以使用矩阵乘法定义递归关系:

For the Fibonacci series, we can define a vector of length 2 to represent adjacent Fibonacci numbers. Using this vector, we can define a recurrence relation with a matrix multiplication:

同样，Tribonacci系列递推关系可以这样写:

Similarly, the Tribonacci series recurrence relation can be written in this way:

唯一的区别是向量和矩阵的大小不同.

The only difference is that the vector and matrix sizes are different.

现在，要计算一个较大的Tribonacci数，我们只需将矩阵相乘n次，即可得到:

Now, to calculate a large Tribonacci number, we just apply the matrix multiplication n times, and we get:

因为我们可以使用幂运算，所以可以有效地计算n(M ⁿ )次幂的矩阵.

The matrix to the power of n (Mⁿ) can be efficiently calculated, because we can use an exponentiation algorithm.

Wikipedia在通过平方求幂中描述了许多用于标量的有效幂运算算法.我们可以对矩阵求幂使用相同的思想.

Many efficient exponentiation algorithms for scalars are described by Wikipedia in Exponentiation by Squaring. We can use the same idea for matrix exponentiation.

我将描述一种简单的方法.首先，我们将n写为二进制数，例如:

I will describe a simple way to do this. First we write n as a binary number, eg:

n = 37 = 100101

然后，通过平方2的前一个幂来计算M到2的每个幂:M ¹ ，M ² = M ¹ M ¹ ，M ⁴ = M ² M ² ，M ⁸ = M ⁴ M ⁴ ，M ¹⁶ = M ⁸ M ⁸ ，M ³² = M ¹⁶ M ¹⁶ ，...

Then, calculate M to each power of 2 by squaring the previous power of 2: M¹, M² = M¹M¹, M⁴ = M²M², M⁸ = M⁴M⁴, M¹⁶ = M⁸M⁸, M³² = M¹⁶M¹⁶, ...

最后，将与n的二进制数字相对应的M的幂相乘.在这种情况下，M ⁿ = M ¹ M ⁴ M ³² .

And finally, multiply the powers of M corresponding to the binary digits of n. In this case, Mⁿ = M¹M⁴M³².

计算完后，我们可以将矩阵与Tribonacci向量相乘得到前三个值，即.

After calculating that, we can multiply the matrix with the Tribonacci vector for the first 3 values, ie.

由于矩阵的大小固定，因此每个矩阵相乘需要固定的时间.我们必须做O(log n)矩阵乘法.因此，我们可以在O(log n)时间内计算出第n个 Tribonacci数.

Because the matrices have fixed size, each matrix multiplication takes constant time. We must do O(log n) matrix multiplications. Thus, we can calculate the n^th Tribonacci number in O(log n) time.

通过计算直到第n个 Tribonacci数(即for (i = 3 to n) {T[i] = T[i-1]+T[i-2]+T[i-3];} return T[n];)的每个Tribonacci数，将其与普通的动态编程方法进行比较，该方法需要花费O(n)的时间.

Compare this to the normal dynamic programming method, where it takes O(n) time, by calculating each Tribonacci number up to the n^th Tribonacci number (ie. for (i = 3 to n) {T[i] = T[i-1]+T[i-2]+T[i-3];} return T[n];).

我假设您知道如何用您选择的语言编写矩阵乘法.

I will assume that you know how to code up matrix multiplication in the language of your choice.

这篇关于具有不同初始值的Tribonacci系列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！