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

Question

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

代码如下: 来自Mark Joshi的Quant Job Interview Quants 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 变量，他们不断地重新分配每个循环(这将是更简单/更具可读性的代码)。

要计算 Fib 数，您需要将最后两个 Fib 数相加。所以我们实际上一次只需要 3 个整数:最后两个 Fib 数，然后是另一个整数来存储我们的新 Fib 数。

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

+--------------------------+
| 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;
}