5.8.4 Числа Фибоначчи

Вычислить N чисел в последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, … , где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.

Самый очевидный способ «решения» задачи состоит в написании рекурсивной функции примерно следующего вида:

function F(X: integer): longint;

begin

if (X = 1) or (X = 2) then F := 1

else F := F(X-1) + F(X-2)

end;

Листинг 5.24 – Рекурсивная функция вычисления чисел Фибоначчи

При этом на шестом-седьмом десятке вызовов программе перестанет хватать временных ресурсов самой современной вычислительной машины. Это происходит по следующим причинам.

Для вычисления F(40) в начале вычисляется F(39) и F(38). Причем F(38) вычисляется заново, не используя значение, которое было вычислено, когда считалось F(39).

То есть значение функции при одном и том же значении аргумента считается много раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:

var D: array[1..100] of longint;

Сперва массив заполняется значениями, которые заведомо не могут быть значениями функции (чаще всего, это «1», но в вполне пригоден 0). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат.

Функция принимает следующий вид:

function F(X: integer): longint;

begin

if D[X] = 0 then

if (X=1) or (X=2) then D[X] := 1

else D[X] := F(X-1) + F(X-2);

F := D[X];

end;

Листинг 5.25 – ДП-функция вычисления чисел Фибоначчи

Этот подход динамического программирования называется подходом «сверху вниз». Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

Можно еще более упростить решение, убрав рекурсию вообще. Для этого необходимо сменить нисходящую логику рассуждения (от того, что надо найти, к тривиальному) на восходящую (соответственно наоборот). В этой задаче такой переход очевиден и описывается простым циклом:

D[1] := 1; D[2] := 1;

For i := 3 to N do

D[i] := D[i-1] + D[i-2];

Листинг 5.26 – Итерационное вычисления чисел Фибоначчи

Здесь использован подход «снизу вверх». Чаще всего, такой способ раза в три быстрее. Однако в ряде случаев такой метод приводит к необходимости решать большее количество подзадач, нежели при рекурсии.

Очень часто для его написания приходится использовать как промежуточный результат нисходящую форму, а иногда безрекурсивная (итеративная) форма оказывается чрезвычайно сложной и малопонятной.

Таким образом, если алгоритм превышает отведенное ему время на тестах большого объема, то необходимо осуществлять доработку этого алгоритма.

Динамическое программирование применимо именно в случаях, ког- да подзадачи не являются незави- симыми или же их зависимость ус- тановить очень трудно. Алгоритм, основанный на динамическом про- граммировании, решает каждую из подзадач всего один раз и запоми- нает ответы для подзадач в специ- альной таблице. Если подзадача встретится еще раз, решение мож- но взять из таблицы.

Как правило, динамическое про- граммирование применяется к за- дачам оптимизации, то есть к та- ким, для которых существует боль- шое количество решений, но их ка- чество определяется каким-либо фактором или параметром. Зада- ча состоит в том, чтобы найти из всех возможных решений то, кото- рое обеспечивает экстремум (мак- симум или минимум) этого пара- метра.

Алгоритм, основанный на динамическом программировании, строит- ся следующим образом:

1. Описывается строение оптимального решения;

2. Строится рекуррентное соотношение, связывающее задачу с ее подзадачами;

3. Делается обход дерева подзадач и вычисляем оптимальное значе- ние искомого параметра для каждой из них, запоминая эти решения в таблице;

4. Строится оптимальное решение с использованием полученной информации.