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

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

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

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

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

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

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

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

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

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

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

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