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 ⁿ )的矩阵，因为我们可以使用求幂算法。

Wikipedia 在Exponentiation by Squaring中描述了许多有效的标量求幂算法。我们可以对矩阵求幂使用相同的想法。

我将描述一个简单的方法来做到这一点。首先我们写成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 ³²。

在计算之后，我们可以将矩阵与前 3 个值的 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];）。

---

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

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先前的项相加，即使它们前面有常数等，它也有效。