Модификации задачи о кузнечике

Задача о кузнечике

Рассмотрим следующую задачу. На числовой прямой сидит кузнечик, который может прыгать вправо на одну или на две единицы. Первоначально кузнечик находится в точке с координатой 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.

Рекурсивное решение

Теперь мы можем оформить решение этой задачи в виде рекурсивной функции:

Но при попытке вычислить решение этой функции для уже не очень больших 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) будет вычисляться уже пять раз. При увеличении глубины рекурсии количество «перекрывающихся» вызовов функций будет расти экспоненциально. То есть одна из причин неэффективности рекурсивного решения — одно и то же значение функции вычисляется несколько раз, так как оно используется для вычисления нескольких других значений функции.

Нерекурсивное решение

На самом деле несложно видеть, что значения рекурсивной функции в данном случае будут совпадать с числами Фибоначчи, так как вычисляются по тем же рекуррентным соотношениям. А для вычисления чисел Фибоначчи можно использовать цикл, а не рекурсию — следующее число Фибоначчи определяется, как сумма двух предыдущих.

Сложность такого решения будет 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). Решение изменится не сильно:

Еще раз модифицируем задачу. Пусть некоторые точки являются «запретными» для кузнечика, он не может прыгать в эти точки. «Карта» запрещенных точек задается при помощи списка Map: если Map[i] == 0 (для языка Pascal — массива Map), то в точку номер i кузнечик не может прыгать, а если Map[i] == 1, то данная точка является разрешенной для кузнечика. Как и в предыдущей задаче, необходимо найти количество маршрутов в точку n.

В данном случае также придется модифицировать вид рекуррентного соотношения: если Map[i] == 0, то F[i] = 0, то есть если точка — «запрещенная», то количество способов попасть в эту точку равно 0, так как нет ни одного допустимого маршрута, заканчивающегося в этой точке. Если же Map[i] == 1, то значение F[i] вычисляется по тем же рекуррентным соотношениям, что и ранее. Получаем следующее решение:

Здесь используется немного другой код для вычисления суммы F[i - 3] + F[i - 2] + F[i - 1] для того, чтобы крайние значения F[1] и F[2] также можно было вычислить при помощи этого кода в основном цикле, а не перед ним.