无法使用模数解释斐波那契解

Question

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

以下是代码：摘自Mark Joshi的Quant Job面试问答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的含义是什么？为了理解C ++，我应该了解有关C ++的任何相关概念吗？非常感谢您的指导

Answer 1

让我们一步一步地走过去...

std::vector<int> v(3);

创建带有3个项目的向量。您在这里的第一个问题应该是“为什么3？”那绝对是我的。

v[0] = 1;
v[1] = 1;

用前两个Fib编号填充前两个向量位置。看起来足够简单...但同样，我们只有3个项目。我们到底将如何在其中存储所有Fib号码？

for (int j = 0; j<=N-2; ++j)

循环N-1次。有意义，那就是我们需要经过多少个Fib号码才能返回到我们要返回的那个。

v[(j+2)%3] = v[(j+1)%3] + v[(j)%3];

啊哈。这就是魔术发生的地方。现在很有意义，为什么我们在向量中只需要3个项目。要计算Fib编号，您需要将最后两个Fib编号相加。因此，我们实际上一次只需要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变量（这将是更简单/更具可读性的代码）。