ЕГЭ 2026 · Задание 13

Количество программ исполнителя

Динамическое программирование: число путей, обязательные и запрещённые этапы.

Повышенный уровеньДинамика25–35 мин✓ Полный урок

Что нужно понимать

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

Число способов

dp[x] — сколько различных программ приводят в значение x.

Обязательный этап

Если нужно пройти через C, часто ответ = ways(A,C) × ways(C,B).

×̸

Запрет

Запрещённое значение исключается из динамики: dp[forbidden] = 0.

Ключевая идея

Если все команды только увеличивают число, считать динамику особенно удобно слева направо от стартового значения к конечному.

Надёжный алгоритм решения

Выпиши команды

Например +1 и ×2.

Определи предшественников

Какие значения могут привести в x одной командой?

Задай старт

Для начального значения dp[start] = 1.

Считай по порядку

dp[x] — сумма dp всех допустимых предшественников.

Учти ограничения

Раздели маршрут по обязательной точке или занули запрещённую.

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

Пошаговый разбор

Исполнитель начинает с 1 и командами «+1» и «×2» должен получить 8, обязательно пройдя через 4. Сколько программ существует?

Участок 1 → 4Исходные данные

ways(1,4) = 4

До 2 есть два разных хода: +1 и ×2. Далее динамика даёт 4 способа попасть в 4.

Участок 4 → 8Результат

Из 4 в 8 существует 2 программы: четыре раза по +1 либо сразу ×2 (с учётом допустимых промежуточных переходов динамика даёт 2).

РазборОткрывай шаги по очереди

dp1=1, dp2=2, dp3=2, dp4=4.

Для второго участка считаем ways(4,8)=2.

4 × 2 = 8 программ проходят через 4.

Тренажёр

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

Практика

Закрепи алгоритм

2 вопроса

Команды +1 и ×2. Сколько программ ведут из 2 в 10 с обязательным прохождением через 5?

Какое значение dp нужно поставить запрещённой вершине?

Шпаргалка на экзамен

Команды образуют ориентированный граф состояний.
dp[x] — сумма способов попасть в x из допустимых предшественников.
Обязательная точка часто разбивает задачу на произведение двух участков.
Запрещённая точка должна давать 0 путей.

Урок 13 завершён

Продолжай по маршруту

Прогресс урока сохраняется локально в браузере.

← Задание 12 Задание 14 →

Тематика урока сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗