Задача 98714
|
Название задачи: Мячик на лесенке. |
 |
Условие
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.Формат входных данных
Одно число 0 < N < 31.
Формат выходных данных
Одно число — количество маршрутов.
Решение
Пусть мячик находится на некоторой ступеньке с номером X. Тогда он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3. Если мы введем функцию F(X), которая определяет число маршрутов со ступеньки X до земли, то F(X) = F(X - 1) + F(X - 2) + F(X - 3). Остается просчитать вручную граничные значения: F(1) = 1, F(2) = 2 (очевидно), F(3) = 4 (3-2-1-0, 3-2-0, 3-1-0, 3-0). Все остальное уже сделано в предыдущей задаче. Чтобы не загромождать функцию, можно присваивания граничных значений сделать заранее, тогда отсечение произойдет автоматически:
Function F(X : integer) : longint;
begin
if D[X] = 0 then D[X] := F(x-1) + F(x-2) + F(x-3);
{для X = 1..3, D[X] > 0 изначально}
F := D[X]
end;
Написание итеративной формы также труда не представляет.
