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

Модифицируем задачу. Пусть кузнечик прыгает на одну, две или три единицы, необходимо также вычислить количество способов попасть в точку n. В рекуррентном соотношении добавится еще одно слагаемое: F(n)=F(n−1)+F(n−2)+F(n−3). И начальные значения для вычисления теперь должны состоять из трех чисел: F(0), F(1), F(2). Решение изменится не сильно:

ПРИМЕР НА ЯЗЫКЕ PYTHON

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]

 

ПРИМЕР НА ЯЗЫКЕ PASCAL

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

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])

 

ПРИМЕР НА ЯЗЫКЕ PASCAL

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:= 1 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] также можно было вычислить при помощи этого кода в основном цикле, а не перед ним.

Одномерное динамическое программирование: наилучший способ

ЗАДАЧА О КУЗНЕЧИКЕ СО СТОИМОСТЯМИ

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением Price[i] списка Price. Необходимо найти минимальную стоимость маршрута кузнечика из точки 0 в точку n.

На этот раз нам необходимо модифицировать определение целевой функции. Пусть C(n) — минимальная стоимость пути из 0 в n. Выведем рекуррентное соотношение для C(n). Чтобы попасть в точку n мы должны попасть в точку n−1 или n−2. Минимальные стоимости этих маршрутов будут равны C(n−1) и C(n−2) соответственно, к ним придется добавить значение Price[n] за прыжок в клетку n. Но из двух клеток n−1 и n−2 нужно выбрать тот маршрут, который имеет наименьшую стоимость.

Получили рекуррентное соотношение:

C(n)=min(C(n−1),C(n−2))+Price(n).

Вычислить значение целевой функции также лучше при помощи динамического программирования, а не рекурсии:

ПРИМЕР НА ЯЗЫКЕ PYTHON

C = [0] * (n + 1)

C[1] = Price[1]

for i in range(2, n + 1):

С[i] = min(C[i — 1], C[i — 2]) + Price[i]

 

ПРИМЕР НА ЯЗЫКЕ PASCAL

var

C, Price: array[0..100] of longint;

i, n: longint;

begin

readln(n);

for i:= 1 to n do

read(Price[i]);

for i:= 0 to n do

C[i]:= 0;

C[1]:= Price[1];

for i:= 2 to n do

C[i]:= min(C[i - 1], C[i - 2]) + Price[i];

writeln(C[n]);

end.

 

После выполнения этого цикла в списке С будет записана минимальная стоимость маршрута для всех точек от 0 до n.

ВОССТАНОВЛЕНИЕ ОТВЕТА

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

Для восстановления ответа будем для каждой точки i запоминать номер точки Prev[i], из которой кузнечик попал в точку i, если он будет передвигаться по пути минимальной стоимости. То есть Prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — это массив предшественников). Как определить Prev[i]? Если C[i−1]<C[i−2], то кузнечик попал в точку i из точки i -1, поэтому Prev[i] = i - 1, иначе Prev[i] = i - 2. Модифицируем алгоритмы вычисления значений целевой функции, одновременно вычисляя значения Prev[i].

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PYTHON:

C = [0] * (n + 1)

C[1] = Price[1]

Prev[1] = 0

for i in range(2, n + 1):

if C[i — 1] < C[i — 2]:

C[i] = C[i — 1] + Price[i]

Prev[i] = i — 1

else:

C[i] = C[i — 2] + Price[i]

Prev[i] = i — 2

 

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PASCAL:

var

C, Price, Prev: array[0..100] of longint;

j, i, n: longint;

begin

readln(n);

for i:= 1 to n do

read(Price[i]);

for i:= 0 to n do

C[i]:= 0;

C[1]:= Price[1];

Prev[1]:= 0;

for i:= 2 to n do

if C[i - 1] < C[i - 2] then begin

C[i]:= C[i - 1] + Price[i];

Prev[i]:= i - 1;

end else begin

C[i]:= C[i - 2] + Price[i];

Prev[i]:= i - 2;

end;

end.

 

Теперь для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь не дойдет до начальной точки с номером 0. Номера всех вершин будем добавлять в список (массив) Path.

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PYTHON:

Path = []

i = n

while i > 0:

Path.append(i)

i = Prev[i]

Path.append(0)

Path = Path[::-1]

 

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PASCAL:

i:= n;

j:= 1;

while i > 0 do

begin

Path[j]:= i;

i:= Prev[i];

inc(j);

end;

Path[j]:= 0;

for i:= j downto 1 do

write(Path[i], ' ');

 

В конце в список Path добавляется начальная вершина номер 0, которая не была обработана в основном цикле, а затем весь список Path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Но можно обойтись и без списка Prev. Мы в любой момент можем определить, из какой точки кузнечик пришел в точку i, если сравним C[i-1] и C[i-2]. Поэтому решение о том, к какой вершине переходить при восстановлении ответа можно принимать непосредственно при восстановлении ответа, сравнив C[i-1] и C[i-2]. Путь восстанавливается через ту вершину, для которой значение C будет меньше.

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PYTHON

Path = []

i = n

while i > 0:

if C[i — 1] < C[i — 2]:

prev = i — 1

else:

prev = i - 2

Path.append(prev)

i = prev

Path.append(0)

Path = Path[::-1]

 

ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ PASCAL:

var

C, Price, Path: array[-1..100] of longint;

j, i, n, prev: longint;

begin

readln(n);

for i:= 1 to n do

read(Price[i]);

for i:= 1 to n do

C[i]:= 0;

C[-1]:= -1;

C[0]:= 0;

C[1]:= Price[1];

for i:= 2 to n do

C[i]:= min(C[i - 1], C[i - 2]) + Price[i];

i:= n;

j:= 1;

Path[j]:= i;

while i > 0 do

begin

inc(j);

if C[i - 1] < C[i - 2] then

prev:= i - 1

else

prev:= i - 2;

Path[j]:= prev;

i:= prev;

end;

Path[j]:= 0;

for i:= j downto 1 do

write(Path[i], ' ');

end.

Линейные задачи

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

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