Задача о кузнечике
Рассмотрим следующую задачу. На числовой прямой сидит кузнечик, который может прыгать вправо на одну или на две единицы. Первоначально кузнечик находится в точке с координатой 0. Определите количество различных маршрутов кузнечика, приводящих его в точку с координатой n.
Обозначим количество маршрутов кузнечика, ведущих в точку с координатой n, как F(n). Теперь научимся вычислять функцию F(n). Прежде всего заметим, что F(0)=1 (это вырожденный случай, существует ровно один маршрут из точки 0 в точку 0 — он не содержит ни одного прыжка), F(1)=1, F(2)=2. Как вычислить F(n)? В точку n кузнечик может попасть двумя способами — из точки n?2 при помощи прыжка длиной 2 и из точки n?1 прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку n?1 и n?2, что позволяет выписать рекуррентное соотношение: F(n)=F(n?2)+F(n?1), верное для всех n?2.
Рекурсивное решение
Теперь мы можем оформить решение этой задачи в виде рекурсивной функции:
| Пример на языке Python | Пример на языке Pascal |
| # неэффективное решение def F(n): if n 2: return 1 else: return F(n — 1) + F(n — 2) | function f(n: longint): longint; begin if n 2 then f := 1 else f := f(n — 1) + f(n — 2); end; |
Но при попытке вычислить решение этой функции для уже не очень больших n, например, для n=40, окажется, что эта функция работает крайне медленно. И при этом время работы функции с увеличением n растет экспоненциально, то есть такое решение неприемлемо по сложности. Причина этого заключается в том, что при вычислении рекурсивной функции подзадачи, для которых вычисляется решение, «перекрываются». То есть для того, чтобы вычислить F(n) нам нужно вызвать F(n?1) и F(n?2). В свою очередь F(n?1) вызовет F(n?2) и F(n?3). То есть функция F(n?2) будет вызвана два раза — один раз это будет сделано при вычислении F(n?1) и один раз — при вычислении F(n?2). Значение F(n?3) будет вычислено уже три раза, а значение F(n?4) будет вычисляться уже пять раз. При увеличении глубины рекурсии количество «перекрывающихся» вызовов функций будет расти экспоненциально. То есть одна из причин неэффективности рекурсивного решения — одно и то же значение функции вычисляется несколько раз, так как оно используется для вычисления нескольких других значений функции.
Нерекурсивное решение
На самом деле несложно видеть, что значения рекурсивной функции в данном случае будут совпадать с числами Фибоначчи, так как вычисляются по тем же рекуррентным соотношениям. А для вычисления чисел Фибоначчи можно использовать цикл, а не рекурсию — следующее число Фибоначчи определяется, как сумма двух предыдущих.
| Пример на языке Python | Пример на языке Pascal |
| F = [0] * (n + 1) F[0] = 1 F[1] = 1 for i in range(2, n + 1): F[i] = F[i — 2] + F[i — 1] | var F: array[0..100] of longint; i, n: longint; begin readln(n); for i := 1 to n do F[i] := 0; F[0] := 1; F[1] := 1; for i := 2 to n do F[i] := F[i — 1] + F[i — 2]; writeln(F[n]); end. |
Сложность такого решения будет O(n). Сложность вычисления уменьшается за счет того, что для каждого промежуточного i значение F(i) вычисляется один раз и сохраняется в списке, чтобы впоследствии использовать это значение несколько раз для вычисления F(i+1) и F(i+2).
Такой прием называетсядинамическим программированием. Динамическое программирование использует те же рекуррентные соотношения, что и рекурсивное решение, но в отличии от рекурсии в динамическом программировании значения вычисляются в цикле и сохраняются в списке. При этом заполнение списка идет от меньших значений к большим, в то время как в рекурсии — наоборот, рекурсивная функция вызывается для больших значений, а затем вызывает сама себя для меньших значений.
Модификации задачи о кузнечике
Модифицируем задачу. Пусть кузнечик прыгает на одну, две или три единицы, необходимо также вычислить количество способов попасть в точку n. В рекуррентном соотношении добавится еще одно слагаемое: F(n)=F(n?1)+F(n?2)+F(n?3). И начальные значения для вычисления теперь должны состоять из трех чисел: F(0), F(1), F(2). Решение изменится не сильно:
| Пример на языке Python | Пример на языке Pascal |
| F = [0] * (n + 1) F[0] = 1 F[1] = F[0] F[2] = F[1] + F[0] for i in range(3, n + 1): F[i] = F[i — 3] + F[i — 2] + F[i — 1] | var F: array[0..100] of longint; i, n: longint; begin readln(n); for i := 1 to n do F[i] := 0; F[0] := 1; F[1] := F[0]; F[2] := F[1] + F[0]; for i := 3 to n do F[i] := F[i — 1] + F[i — 2] + F[i — 3]; writeln(F[n]); end. |
Еще раз модифицируем задачу. Пусть некоторые точки являются «запретными» для кузнечика, он не может прыгать в эти точки. «Карта» запрещенных точек задается при помощи списка Map: если Map[i] == 0 (для языка Pascal — массива Map), то в точку номер i кузнечик не может прыгать, а если Map[i] == 1, то данная точка является разрешенной для кузнечика. Как и в предыдущей задаче, необходимо найти количество маршрутов в точку n.
В данном случае также придется модифицировать вид рекуррентного соотношения: если Map[i] == 0, то F[i] = 0, то есть если точка — «запрещенная», то количество способов попасть в эту точку равно 0, так как нет ни одного допустимого маршрута, заканчивающегося в этой точке. Если же Map[i] == 1, то значение F[i] вычисляется по тем же рекуррентным соотношениям, что и ранее. Получаем следующее решение:
| Пример на языке Python | Пример на языке Pascal |
| F = [0] * (n + 1) F[0] = 1 for i in range(1, n + 1): if Map[i] == 0: F[i] = 0 else: F[i] = sum(F[max(0, i-3):i]) | var F, Map: array[0..100] of longint; i, n: longint; begin readln(n); for i := 1 to n do read(Map[i]); F[0] := 1; F[1] := Map[1]*F[0]; F[2] := Map[2]*(F[1] + F[0]); for i := 3 to n do F[i] := Map[i]*(F[i — 1] + F[i — 2] + F[i — 3]); writeln(F[n]); end. |
Здесь используется немного другой код для вычисления суммы F[i — 3] + F[i — 2] + F[i — 1] для того, чтобы крайние значения F[1] и F[2] также можно было вычислить при помощи этого кода в основном цикле, а не перед ним.
