Блог

Я задаю этот вопрос о кодировании, в котором вас просят ввести числа 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; 
}
  

Хотя программа, которую вы написали, в значительной степени является примером рекурсии в образовании, это действительно чертовски плохой алгоритм, как вы выяснили. Попробуйте записать дерево вызовов fib(7) , и вы обнаружите, что количество выполняемых вами вызовов резко возрастает.

Есть много способов ускорить ее и не допустить повторного вычисления одних и тех же значений снова и снова. Кто-то уже ссылался на кучу алгоритмов в комментариях — простой цикл может легко сделать его линейным в N вместо экспоненциального.

Однако одна из проблем заключается в том, что числа Фибоначчи растут довольно быстро: вы можете удерживать fib(93) 64-битное целое число, но fib(94) переполняет его.

Однако вам не нужно N-е число Фибоначчи — вам нужен N-й мод M. Это немного меняет задачу, потому что, пока M меньше MAX_INT_64 / 2, вы можете вычислять fib(N) mod M для любого N.

Обратите свое внимание на модульную арифметику и отношения соответствия. В частности, для добавления, в котором говорится (изменен синтаксис на 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

Это означает, что вы можете поместить оператор по модулю в середину вашего алгоритма, чтобы вы никогда не складывали большие числа вместе и никогда не переполнялись. Таким образом, вы можете легко вычислить, например. fib(10000) mod 237 .

Существует одна простая оптимизация при вызове 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.

1-е наблюдение заключается в том, что вы можете превратить рекурсию в простой цикл:

 #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];
};
  

Другим вариантом может быть алгебраическая формула.

приветствия, FM.