Pull to refresh

Нахождение чисел Фибоначчи

Reading time 2 min
Views 23K
Доброго времени суток!
Сегодня я хотел бы рассказать о методе разрешения некоторых рекуррентностей и разобрать классический пример на эту тему.
Начнем с определения рекуррентной формулы:
Рекуррентная формула — формула вида , выражающая каждый член последовательности через предыдущих членов.

Рассмотрим задачу, которая формулируется очень просто: нам нужно найти N-ое число Фибоначчи по модулю P, где N <= 10^15, P <= 10^9. Как видно из ограничений, складывать числа тривиальным методом за О(n) не получится, нужно придумывать более быстрый алгоритм, в этой статье речь пойдет об операторном методе с асимптотикой O(log N). Пусть у нас есть вектор столбец , — n-ое число Фибоначчи, постараемся подобрать оператор такой, что будет выполняться равенство . Для чисел Фибоначчи легко найти матрицу этого оператора, если вспомнить рекуррентную формулу , матрица равна , действительно . А учитывая то, что наш оператор подходит не только для первых чисел Фибоначчи, а и для всех, то есть , имеем . Значит мы можем вычислить ответ, возведя матрицу нашего оператора в N-ую степень, для этого воспользуемся алгоритмом логарифмического возведения в степень. Вот код, написанный на java:
Copy Source | Copy HTML
  1. private static long getFibb(int n) {
  2.     long a11 = 1, a12 = 1, a21 = 1, a22 =  0; //матрица оператора
  3.     long r11 = 1, r12 =  0; //вектор-столбец результа
  4.     long q11 =  0, q12 =  0, q21 =  0, q22 =  0; //вспомогательная матрица при перемножении
  5.     while (n >  0) {
  6.         if ((n&1)==1) {
  7.             q11 = (r11 * a11 + r12 * a21) % MOD;
  8.             q12 = (r11 * a12 + r12 * a22) % MOD;
  9.             r11 = q11;
  10.             r12 = q12;
  11.         }
  12.         q11 = (a11 * a11 + a12 * a21) % MOD;
  13.         q12 = (a11 * a12 + a12 * a22) % MOD;
  14.         q21 = (a21 * a11 + a22 * a21) % MOD;
  15.         q22 = (a21 * a12 + a22 * a22) % MOD;
  16.         a11 = q11;
  17.         a12 = q12;
  18.         a21 = q21;
  19.         a22 = q22;
  20.  
  21.         n >>= 1;
  22.     }
  23.     return r12; //возвращаем Fn
  24. }

Осталось только выдать наш ответ:
Copy Source | Copy HTML
  1. out.println(getFibb(N));

Спасибо за внимание.
Tags:
Hubs:
+7
Comments 39
Comments Comments 39

Articles