Подсчёт маршрутов Кузнечика
Подсчёт маршрутов Кузнечика — это определение количества различных последовательностей прыжков, с помощью которых исполнитель попадает из начальной клетки в конечную. Обычно число маршрутов вычисляют последовательно, используя уже найденные значения для предыдущих клеток.
В базовом варианте Кузнечик начинает в клетке 1 и может прыгнуть на 1 или на 2 клетки вправо. Обозначим через \(F(n)\) число способов попасть в клетку \(n\). Последний прыжок в клетку \(n\) мог быть сделан из клетки \(n-1\) или из клетки \(n-2\). Поэтому достаточно сложить число способов попасть в эти две клетки.
Начальные значения зависят от условия. Если стартовая клетка считается клеткой 0, удобно взять \(F(0)=1\): находиться в начале можно единственным способом — ещё не сделав ни одного прыжка. Тогда \(F(1)=1\), \(F(2)=2\), \(F(3)=3\), \(F(4)=5\).
Кузнечик прыгает на 1 или 2 клетки. Число маршрутов в клетку 4 равно \(F(4)=F(3)+F(2)=3+2=5\). Последовательности длин прыжков: \(1+1+1+1\), \(1+1+2\), \(1+2+1\), \(2+1+1\), \(2+2\).
Число маршрутов — не то же самое, что длина кратчайшего маршрута и не количество прыжков. Например, до клетки 4 можно добраться за два прыжка, но всего маршрутов пять. Общий способ решения относится к динамике для маршрутов Кузнечика, а описание самого исполнителя дано в маршруте Кузнечика.
Кузнечик прыгает на 1 или 2 клетки. Сколько маршрутов ведёт из клетки 0 в клетку 3?
Главное
- Число маршрутов считают по последнему прыжку: складывают способы попасть в клетки, из которых он мог начаться.
- Для прыжков на 1 или 2 клетки используется формула \(F(n)=F(n-1)+F(n-2)\).
- Начальные значения нужно выбрать по условию задачи; часто используют \(F(0)=1\) и \(F(1)=1\).