c++ - 如何加快此程序以找到斐波那契数列

Question

我正在做这个编码问题，他们要求您输入数字 N 和 M，并且您应该输出第 N 个斐波那契数 mod M。我的代码运行速度很慢，我想学习如何加快速度。

#include<bits/stdc++.h> 
using namespace std; 

long long fib(long long N) 
{ 
    if (N <= 1) 
        return N; 
    return fib(N-1) + fib(N-2); 
} 

int main () 
{ 
    long long N;
    cin >> N;
    long long M;
    cin >> M;
    long long b;
    b = fib(N) % M;
    cout << b; 
    getchar(); 
    return 0; 
}

Answer 1

虽然您编写的程序几乎是教育中递归的首选示例，但正如您所发现的那样，它确实是一个非常糟糕的算法。尝试编写 fib(7) 的调用树你会发现你调用的电话数量急剧增加。
有很多方法可以加速它并防止它一遍又一遍地重新计算相同的值。有人已经在评论中链接到一堆算法——一个简单的循环可以很容易地使它在 N 中成为线性而不是指数。
这样做的一个问题是斐波那契数增长非常快:你可以持有 fib(93) 64 位整数，但 fib(94)溢出它。
但是，您不需要第 N 个斐波那契数 - 您需要第 N 个 mod M。这会稍微改变挑战，因为只要 M 小于 MAX_INT_64/2，那么您就可以计算 fib(N) mod M对于任何 N。
关注 Modular arithmetic和全等关系。特别是添加的那个，它说(更改为 C++ 语法并简化了一点):
如果 a1 % m == b1和 a2 % m == b2然后 (a1 + a2) % m == (b1 + b2) % m或者，举个例子:17 % 3 == 2 , 22 % 3 == 1 => (17 + 22) % 3 == (2 + 1) % 3 == 3 % 3 == 0这意味着您可以将模运算符放在算法的中间，这样您就永远不会将大数相加并且永远不会溢出。这样您就可以轻松计算 f.ex。 fib(10000) mod 237 .