Находим N’е число Фибоначчи тремя способами за приемлемое время: основы динамического программирования

Задача: посчитать N-е число последовательности, в которой каждый элемент равен сумме двух предыдущих. Такая последовательность называется последовательностью Фибоначчи: 1, 1, 2, 3, 5, 8…

Очень часто на разнообразных олимпиадах попадаются задачи вроде этой, которые, как думается на первый взгляд, можно решить с помощью простого перебора. Но если мы подсчитаем количество возможных вариантов, то сразу убедимся в неэффективности такого подхода: например, простая рекурсивная функция, приведенная ниже, будет потреблять существенные ресурсы уже на 30-ом числе Фибоначчи, тогда как на олимпиадах время решения часто ограничено 1-5 секундами.

int fibo(int n)
{
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

Давайте подумаем, почему так происходит. Например, для вычисления fibo(30) мы сначала вычисляем fibo(29) и fibo(28). Но при этом наша программа «забывает», что fibo(28) мы уже вычисляли при поиске fibo(29).

Основная ошибка такого подхода «в лоб» в том, что одинаковые значения аргументов функции исчисляются многократно — а ведь это достаточно ресурсоемкие операции. Избавиться от повторяющихся вычислений нам поможет метод динамического программирования — это прием, при использовании которого задача разбивается на общие и повторяющиеся подзадачи, каждая из которых решается только 1 раз — это значительно повышает эффективность программы. Этот метод подробно описан в нашей статье, там же есть и примеры решения других задач.

Самый просто вариант улучшения нашей функции — запоминать, какие значения мы уже вычисляли. Для этого нужно ввести дополнительный массив, который будет служить как бы «кэшем» для наших вычислений: перед вычислением нового значения мы будем проверять, не вычисляли ли его раньше. Если вычисляли, то будем брать из массива готовое значение, а если не вычисляли — придётся считать его на основе предыдущих и запоминать на будущее:

int cache[100];

int fibo(int n)
{
    if (cache[n] == 0) {
        if (n == 1 || n == 2) {
            cache[n] = 1;
        } else {
            cache[n] = fibo(n - 1) + fibo(n - 2);
        }
    }

    return cache[n];
}

Так как в данной задаче для вычисления N-ого значения нам гарантированно понадобится (N-1)-е, то не составит труда переписать формулу в итерационный вид — просто будем заполнять наш массив подряд до тех пор, пока не дойдём до нужной ячейки:

cache[0] = 1;
cache[1] = 1;

for (int i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
}

cout << cache[n-1];

Теперь мы можем заметить, что когда мы вычисляем значение F(N), то значение F(N-3) нам уже гарантированно никогда не понадобится. То есть нам достаточно хранить в памяти лишь два значения — F(N-1) и F(N-2). Причём, как только мы вычислили F(N), хранение F(N-2) теряет всякий смысл. Попробуем записать эти размышления в виде кода:

//Два предыдущих значения:
int cache1 = 1;
int cache2 = 1;
//Новое значение
int cache3;

for (int i = 2; i <= n; i++) {
    cache3 = cache1 + cache2; //Вычисляем новое значение

    //Абстрактный cache4 будет равен cache3+cache2
    //Значит cache1 нам уже не нужен?..

    //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации.
    //cache5 = cache4 - cache3 => через итерацию потеряет актуальность cache2, т.е. он и должен стать cache1

    //Иными словами, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n).
    //Пусть N=n+1 (номер, который мы вычисляем на следующей итерации). Тогда n-2=N-3, n-1=N-2, n=N-1.
    //В соответствии с новыми реалиями мы и переписываем значения наших переменных:

    cache1 = cache2;
    cache2 = cache3;
}

cout << cache3;

Бывалому программисту понятно, что код выше, в общем-то ерунда, так как cache3 никогда не используется (он сразу записывается в cache2), и всю итерацию можно переписать, используя всего одно выражение:

cache[0] = 1;
cache[1] = 1;
 
for (int i = 2; i <= n; i++) {
    cache[i%2] = cache[0] + cache[1];
    //При i=2 устареет 0-й элемент
    //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый
    //При i=4 последним элементом мы обновляли cache[1], значит ненужное старьё сейчас в cache[0]
    //Интуитивно понятно, что так будет продолжаться и дальше
}
 
cout << cache[n%2];

Для тех, кто не может понять, как работает магия с остатком от деления, или просто хочет увидеть более неочевидную формулу, существует ещё одно решение:

int x = 1;
int y = 1;

for (int i = 2; i < n; i++) {
   y = x + y;
   x = y - x;
}

cout << "Число Фибоначчи: " << y;

Попробуйте проследить за выполнением этой программы: вы убедитесь в правильности алгоритма.

P.S. Вообще, существует единая формула для вычисления любого числа Фибоначчи, которая не требует никаких итераций или рекурсии:

const double SQRT5 = sqrt(5);
const double PHI = (SQRT5 + 1) / 2;

int fibo(int n){
    return int(pow(PHI, n) / SQRT5 + 0.5);
}

Но, как можете догадаться, подвох в том, что цена вычисления степеней нецелых чисел довольно велика, как и их погрешность.