Зимняя школа в "Эврике"

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