如何在斐波那契数列上使用二维数组乘以矩阵？

Question

我遇到的问题是我不确定如何将同一个矩阵一遍又一遍地相乘。我想要实现的是我希望能够更新矩阵。这是我的代码：

int fib3(int a, int b, int n) {
int num[2][2] = { {0,1}, {1,1} };
const int num2[2][2] = { {0,1}, {1,1} };
int factArray[2][1] = { {0}, {1} };
if (n == 0) {
    return a;
}
else if (n == 1) {
    return b;
}
else {

    for (int i = 0; i <= n; i++) {
        num[0][0] = ((num2[0][0] * 0) + num2[0][1] * 1);
        num[0][1] = ((num2[0][0] * 1) + num2[0][1] * 1);
        num[1][0] = ((num2[1][0] * 0) + num2[1][1] * 1);
        num[1][1] = ((num2[1][0] * 1) + num2[1][1] * 1);
    }


    factArray[0][0] = ((num[0][0] * factArray[0][0]) + num[0][1] * factArray[1][0]);
    factArray[1][0] = ((num[1][0] * factArray[0][0]) + num[1][1] * factArray[1][0]);

    return factArray[0][0];
}

这里我会把前面的矩阵乘以一个常量矩阵，但我不确定如何更新矩阵。

所以矩阵被提升到某种幂。

例如，我想找到 f(5) 第 5 个斐波那契数列，它应该是 5，而我在编程中得到的结果是 1。

Answer 1

矩阵表示中的公式主要用于理论分析。诀窍是您始终可以在向量中包含序列的两个元素，而不必引用序列的较早元素。但是，与使用递归公式相比，我看不到实现它的好处。考虑

 | 1 1 |   | a |    | a+b |
 | 1 0 | * | b | =  | a   |

因此矩阵乘法实际上完全相同：添加最后两个元素，记住当前元素 (a)。

也就是说，您的代码有一些问题：

您传递了 a 和 b，但您只将它们用于序列的第一个和第二个元素。您不需要 a 和 b。初始值已经在矩阵的起始值中。
你有一个循环，但在每次迭代中你计算相同的值并将它们写入相同的数组元素。
我无法真正理解您代码的逻辑。为什么循环后还有一个乘法？ matrix formula 简而言之就是 "take some starting vector, apply a matrix n times, done"。老实说，我在你的代码中找不到任何地方 ;)

如果你坚持使用矩阵乘法，我建议远离 c 风格的数组。他们不喜欢被传递。请改用 std::array。我有点反感嵌套，因此我建议使用

constexpr size_t N = 2;
using matrix = std::array<int,N*N>;
using vector = std::array<int,N>;

std::array可以无痛退货：

vector multiply(const matrix& a,const vector& b) {
    vector result;
    auto ma = [&a](size_t row,size_t col) { return a[row*N+col];};    
    result[0] = ma(0,0)*b[0] + ma(0,1)*b[1];
    result[1] = ma(1,0)*b[0] + ma(1,1)*b[1];
    return result;
}

现在应该可以直接实现斐波那契数列了。

Spoiler Alert

如何在斐波那契数列上使用二维数组乘以矩阵？

How to multiply matrices using 2D Array on Fibonacci Sequence?

c++

fibonacci