我如何加速这个程序来找到斐波那契数列

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 然后你可以为任何 N.

计算 fib(N) mod M

将注意力转向 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

这意味着您可以将 modulo 运算符放在算法的中间，这样您就不会将大数加在一起也不会溢出。这样就可以轻松计算出f.ex。 fib(10000) mod 237.

Answer 2

在不计算重复值的情况下调用 fib 有一个简单的优化。同样使用循环而不是递归可以加快这个过程：

int fib(int N) {
    int f0 = 0;
    int f1 = 1;
    for (int i = 0; i < N; i++) {
         int tmp = f0 + f1;
         f0 = f1;
         f1 = tmp;
    }
    return f1;
}

您可以在此基础上应用@Frodyne 提出的模运算符。

Answer 3

第一个观察结果是您可以将递归变成一个简单的循环：

#include <cstdint>

std::uint64_t fib(std::uint16_t n) {
    if (!n)
        return 0;
    std::uint64_t result[]{ 0,1 };
    bool select = 1;
    for (auto i = 1; i < n; ++i , select=!select)
    {
        result[!select] += result[select];
    };
    return result[select];
};

接下来就可以记忆了：

#include <cstdint>
#include <vector>

std::uint64_t fib(std::uint16_t n) {
    static std::vector<std::uint64_t>  result{0,1};
    if (result.size()>n)
        return result[n];
    std::uint64_t back[]{ result.crbegin()[1],result.back() };
    bool select = 1;
    result.reserve(n + 1);
    for (auto i=result.size(); i < result.capacity();++i, select = !select)
        result.push_back(back[!select] += back[select]);
    return result[n];
};

另一种选择是代数公式。

干杯，调频.

我如何加速这个程序来找到斐波那契数列

How do I speed up this program to find fibonacci sequence

c++

fibonacci

execution-time