Информатика · ЕГЭ · 4 мин чтения

Как посчитать программы исполнителя с запрещённым числом?

Редакция Алгоса · Обновлено

Короткий ответ

Если команды исполнителя только увеличивают положительное число, можно считать способы по возрастанию состояний. Для каждого числа сложи количество программ, которые приходят в него последним разрешённым действием. Начальному числу присвой один способ — пустую программу. Запрещённому числу присвой ноль: через него не должен проходить ни один допустимый путь.

Разберись, что нужно найти

Пусть исполнитель начинает с 1 и умеет прибавлять 1 или 2. Нужно получить 6, не посещая 4. Обозначим ways[x] количество допустимых программ до числа x. В число x можно прийти из x − 1 командой +1 или из x − 2 командой +2. Эти программы различаются последней командой, поэтому их количества складываются.

Связь условия задачи с нужным действием
Что дано или требуетсяКак это использовать
Начальное состояниеОдин способ: ещё не выполнить команд
Обычное состояние xways[x − 1] + ways[x − 2]
Запрещённое состояниеНоль способов

Проследи решение на конкретных данных

Получаем ways[1] = 1. До 2 есть один путь, до 3 — два: +1,+1 и +2. Число 4 запрещено, поэтому ways[4] = 0, даже если без запрета до него можно было бы добраться. До 5 остаются только два пути через 3, а до 6 — два пути через 5.

Промежуточные результаты разобранного примера
ШагРезультат
Состояния 1, 2, 31, 1, 2 способа
Состояние 40 способов
Состояния 5, 62, 2 способа
Пример с объяснением

Таблица значений для 1, 2, 3, 4, 5, 6 равна 1, 1, 2, 0, 2, 2. Две программы до цели: +2,+2,+1 и +1,+1,+2,+1. Обе обходят число 4. Пустая программа учитывается только в старте; она не означает, что до каждого числа автоматически существует один способ.

Проверь границы способа и реши сам

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

Самопроверка: для тех же команд +1 и +2 посчитай программы из 1 в 5, если запрещено число 3. Заполни состояния по порядку. Можно ли перепрыгнуть через запрещённое число командой +2, если правило запрещает именно посещение?

Ответ и почему так

Получаем ways[1] = 1, ways[2] = 1, ways[3] = 0, ways[4] = 1, ways[5] = 1. Единственная программа: +1,+2,+1. Она идёт 1 → 2 → 4 → 5. Перепрыгнуть через 3 можно: среди состояний после команд тройка не появляется.

Что запомнить

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

Попробовать на Алгосе

Программирование для ЕГЭ

Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы