Динамика для маршрутов Кузнечика

Исполнитель Кузнечик перемещается по клеткам числовой оси и должен попасть из начальной клетки в конечную. Число маршрутов удобно считать по значениям предыдущих клеток: для каждой клетки запоминаем, сколькими способами в неё можно попасть, и используем эти значения дальше.

Модель задачи и правила движения

Клетки обычно нумеруются целыми числами слева направо: \(1, 2, 3, \ldots, n\). Кузнечик начинает в клетке \(s\) и заканчивает в клетке \(f\), причём \(s<f\). Разрешённые прыжки задаются условием задачи: например, можно прыгать на 1 или 2 клетки вправо, на 1 или 3 клетки, либо выполнять несколько разных команд.

Если Кузнечик движется только вправо, то циклов нет: попасть из клетки с большим номером обратно в меньшую невозможно. Это позволяет считать маршруты слева направо. Такая схема является частным случаем задач про маршрут Кузнечика, а формулу перехода полезно сравнить с рекуррентной формулой маршрутов Кузнечика.

Динамика по клеткам

Введём массив \(ways\). Значение \(ways[i]\) — количество маршрутов из стартовой клетки в клетку \(i\). Сначала задаём начальное состояние: в стартовой клетке находится один маршрут — маршрут нулевой длины. Поэтому \(ways[s]=1\).

Затем клетки рассматриваются по возрастанию номера. Для каждой клетки \(i\) перебираем разрешённые длины прыжка \(j\). Если клетка \(i-j\) существует и достижима, то каждый маршрут в неё можно продолжить прыжком в \(i\).

Если начало равно 1, а разрешены прыжки на 1 и 2 клетки, получаем знакомую формулу \(ways[i]=ways[i-1]+ways[i-2]\). Но важнее понимать не название последовательности, а смысл каждого слагаемого: последний прыжок в клетку \(i\) либо имел длину 1, либо длину 2.

Таблица значений и порядок вычислений

Таблица помогает не запутаться в индексах. В первой строке записывают номера клеток, во второй — значения \(ways\). Каждое новое значение вычисляется только после того, как готовы все нужные предыдущие значения.

Для прыжков на 1 и 2 клетки здесь старт — клетка 1. Например, в клетку 5 можно прийти из 4 или из 3, поэтому \(ways[5]=ways[4]+ways[3]=3+2=5\).

Разобранный пример: прыжки на 1, 2 или 3 клетки

Пусть Кузнечик начинает в клетке 2 и должен попасть в клетку 9. Разрешены прыжки вправо на 1, 2 или 3 клетки. Требуется найти число маршрутов.

Тот же расчёт можно выполнить программой. Перед циклом все значения должны быть нулевыми, а стартовая клетка — отмечена единицей. Такой подход особенно полезен в больших задачах и связан с темой оптимизации алгоритма.

start = 2
finish = 9
jumps = [1, 2, 3]
ways = [0] * (finish + 1)
ways[start] = 1

for cell in range(start + 1, finish + 1):
    for jump in jumps:
        previous = cell - jump
        if previous >= start:
            ways[cell] += ways[previous]

print(ways[finish])

Недостижимые клетки и препятствия

Если некоторые клетки запрещены, в них нельзя заходить. Их значение принудительно равно нулю, даже если из предыдущих клеток туда ведут прыжки. При вычислении следующей клетки запрещённая клетка автоматически не добавляет маршруты.

Например, если клетка 5 закрыта, нужно установить \(ways[5]=0\) и не выполнять для неё обычное сложение. Подробные варианты с закрытыми клетками разобраны на странице препятствия на поле Кузнечика. При ручном подсчёте удобно отмечать такие клетки крестиком или нулём.

Как распознать и решить задачу на экзамене

В заданиях ЕГЭ-25 и ЕГЭ-26 часто требуется найти количество программ или маршрутов, удовлетворяющих правилам переходов. Перед вычислениями выпишите три вещи: старт, финиш и все разрешённые ходы. Затем составьте таблицу или массив.

1. Обозначьте \(ways[i]\) как число способов попасть в клетку \(i\).
2. Поставьте единицу в стартовую клетку, остальные значения пока сделайте нулевыми.
3. Для каждой следующей клетки перечислите возможные клетки, откуда в неё можно попасть.
4. Сложите значения этих предшественников; для запрещённой клетки запишите ноль.
5. Прочитайте значение в финишной клетке и проверьте первые 2–3 перехода вручную.

Если в условии встречаются дополнительные ограничения, например обязательное посещение клетки, полезно разделить маршрут на части. Число маршрутов через клетку \(k\) равно произведению числа маршрутов от старта до \(k\) и от \(k\) до финиша, если эти части независимы. Для более общего подсчёта можно обратиться к странице подсчёт маршрутов Кузнечика. Проверять рассуждение удобно приёмами со страницы проверка алгоритма.

Быстрая проверка