algorithm - 具有不同初始值的 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

矩阵乘法涉及使用矩阵递推关系。

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

同理，Tribonacci 级数递归关系可以这样写:

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

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

n 次方矩阵 (Mⁿ) 可以高效计算，因为我们可以使用求幂算法。

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

我将描述一个简单的方法来做到这一点。首先我们把n写成一个二进制数，eg:

n = 37 = 100101

然后，通过对 2 的前次方的平方计算 M 的每个 2 次方:M¹, M² = M¹M ¹, M⁴ = M²M², M⁸ = M< sup>4M⁴, M¹⁶ = M⁸M⁸, M ³² = M¹⁶M¹⁶, ...

最后，乘以n的二进制数字对应的M次方。在这种情况下，Mⁿ = M¹M⁴M³²。

计算之后，我们可以将矩阵与前 3 个值的 Tribonacci 向量相乘，即。

因为矩阵的大小是固定的，所以每次矩阵乘法都需要常数时间。我们必须执行 O(log n) 矩阵乘法。因此，我们可以在 O(log n) 时间内计算出第 n Tribonacci 数。

将此与普通的动态规划方法进行比较，后者需要 O(n) 时间，通过计算每个 Tribonacci 数直到第 n^th Tribonacci 数(即。 for (i = 3 to n) {T[i] = T[i-1]+T[i-2]+T[i-3];} 返回 T[n];) .

---

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