Рекуррентная формула маршрутов Кузнечика
Рекуррентная формула маршрутов Кузнечика позволяет вычислить, сколькими способами исполнитель может попасть в каждую клетку. Число маршрутов для текущей клетки получают сложением чисел маршрутов для всех клеток, из которых в неё разрешён шаг Кузнечика.
Пусть \(F(n)\) — число маршрутов из начальной клетки в клетку с номером \(n\). Если Кузнечик может прийти в \(n\) из клеток \(n-d_1,n-d_2,\ldots,n-d_k\), то каждый маршрут в клетку \(n\) заканчивается одним из этих переходов. Поэтому достаточно сложить количества маршрутов в предшествующие клетки.
Сначала задают начальные значения. Для стартовой клетки обычно принимают \(F(s)=1\): существует один пустой маршрут, который уже находится в начале. Для недостижимой или запрещённой клетки значение равно \(0\). Затем значения вычисляют слева направо, пока не будет достигнута конечная клетка. Такой способ является частью динамики для маршрутов Кузнечика.
Кузнечик стоит в клетке \(1\) и за один ход прыгает на \(+1\) или \(+2\). Тогда \(F(1)=1\), \(F(2)=F(1)=1\), \(F(3)=F(2)+F(1)=2\), \(F(4)=F(3)+F(2)=3\). Значит, в клетку \(4\) ведут три маршрута: \(1\to2\to3\to4\), \(1\to2\to4\) и \(1\to3\to4\).
Рекуррентная формула — это математическое правило вычисления значений, а не обязательно рекурсивное соотношение рекурсии в программе. В задачах ЕГЭ её часто реализуют циклом и массивом, чтобы не пересчитывать одни и те же клетки.
Кузнечик прыгает на \(+1\) или \(+3\). Как вычислить число маршрутов в клетку \(n\)?
Главное
- Число маршрутов в клетку равно сумме чисел маршрутов во все разрешённые предыдущие клетки.
- Стартовая клетка обычно имеет значение \(1\), запрещённая или недостижимая — \(0\).
- Значения вычисляют последовательно, чаще всего циклом и массивом.