无法使用模数理解斐波那契解决方案

Question

我得到了以下生成斐波那契数列的代码，但我无法理解它背后的数学方法是什么？

代码如下：来自 Mark Joshi 的 Quant Job Interview Quants and Answers 5.3

int Fib2(int N):
{
    std::vector<int> v(3);
    v[0] = 1;
    v[1] = 1;
    for (int j = 0; j<=N-2; ++j)
      v[(j+2)%3] = v[(j+1)%3] + v[(j)%3];
    return v[N%3];
}

还有，上面代码中的std::vector是什么意思？

Answer 1

一个std::vector是一个容器（类似于数组）。在本例中，它存储了 3 个整数。从本质上讲，他们试图花哨而不使用 3 个 int 变量，他们不断地重新分配每个循环（这将是 simpler/more 可读代码）。

要计算斐波纳契数，您需要将最后两个斐波纳契数相加。所以我们真的一次只需要 3 个整数：最后两个 Fib 数，然后是另一个整数来存储我们新的 Fib 数。

我们在这里使用模数来告诉我们哪个索引是哪个。所以向量在循环中看起来像这样：（星号表示我们刚刚计算和分配的索引）

+--------------------------+
| Fib(0) | Fib(1) | *Fib(2)|
+--------------------------+
|   1    |   1    |    2   |
+--------------------------+

+--------------------------+
|*Fib(3) | Fib(1) | Fib(2) |
+--------------------------+
|   3    |   1    |    2   |
+--------------------------+

+--------------------------+
| Fib(3) | *Fib(4) | Fib(2)|
+--------------------------+
|   3    |   5     |   2   |
+--------------------------+

etc...

使用 3 个整数（功能上与此相同）的更简单实现如下所示：

int Fib2(int N) {
    int last, curr;
    last = curr = 1;

    for (int j = 0; j<=N-2; ++j) {
      int newest = last + curr;
      last = curr, curr = newest;
    }
    return curr;
}

无法使用模数理解斐波那契解决方案

Cannot Make Sense of Fibonacci Solution Using Modulo

c++

fibonacci