Информатика · ЕГЭ · 4 мин чтения
Как посчитать программы исполнителя с запрещённым числом?
Редакция Алгоса · Обновлено
Короткий ответ
Если команды исполнителя только увеличивают положительное число, можно считать способы по возрастанию состояний. Для каждого числа сложи количество программ, которые приходят в него последним разрешённым действием. Начальному числу присвой один способ — пустую программу. Запрещённому числу присвой ноль: через него не должен проходить ни один допустимый путь.
Разберись, что нужно найти
Пусть исполнитель начинает с 1 и умеет прибавлять 1 или 2. Нужно получить 6, не посещая 4. Обозначим ways[x] количество допустимых программ до числа x. В число x можно прийти из x − 1 командой +1 или из x − 2 командой +2. Эти программы различаются последней командой, поэтому их количества складываются.
| Что дано или требуется | Как это использовать |
|---|---|
| Начальное состояние | Один способ: ещё не выполнить команд |
| Обычное состояние x | ways[x − 1] + ways[x − 2] |
| Запрещённое состояние | Ноль способов |
Проследи решение на конкретных данных
Получаем ways[1] = 1. До 2 есть один путь, до 3 — два: +1,+1 и +2. Число 4 запрещено, поэтому ways[4] = 0, даже если без запрета до него можно было бы добраться. До 5 остаются только два пути через 3, а до 6 — два пути через 5.
| Шаг | Результат |
|---|---|
| Состояния 1, 2, 3 | 1, 1, 2 способа |
| Состояние 4 | 0 способов |
| Состояния 5, 6 | 2, 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 можно: среди состояний после команд тройка не появляется.
Что запомнить
При возрастающих командах считай способы по порядку состояний; запрещённому состоянию присвой ноль.
Попробовать на Алгосе
Программирование для ЕГЭ
Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.
Перейти к курсу Все курсы