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