Tribonacci系列具有不同的初始值

Question

如果初始值是一些任意数字,如果1,2 3即T(1)= 1,T(2)= 2和T(3)= 3,如何用矩阵乘法法找到第n个tribonacci数.

如果T(n)= T(n-1)+ T(n-2)+ T(n-3)那么如果n非常大,如何找到T(n),如果有人能用矩阵解释我会很感激乘法方法.如何构造初始矩阵.

Answer 1

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

对于Fibonacci系列,我们可以定义长度为2的向量来表示相邻的Fibonacci数.使用此向量,我们可以使用矩阵乘法定义递归关系:

同样,Tribonacci系列递归关系可以这样写:

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

现在,为了计算一个大的Tribonacci数,我们只应用矩阵乘法n次,我们得到:

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

维基百科在Squaring的Exponentiation中描述了许多用于标量的有效取幂算法.我们可以使用相同的思想进行矩阵求幂.

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

n = 37 = 100101

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

最后,乘以对应于二进制数字的M的幂n.在这种情况下,M ⁿ = M ¹ M ⁴ M ³².

在计算完之后,我们可以将矩阵与前三个值的Tribonacci向量相乘,即.

因为矩阵具有固定的大小,所以每个矩阵乘法需要恒定的时间.我们必须进行O(log n)矩阵乘法.因此,我们可以及时计算第n ^个 Tribonacci数O(log n).

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

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