Задание13

Подсчёт программ исполнителя

ЕГЭ по информатике · задание 13 из 27

ЕГЭ-2027 · проект ФИПИ · сверено 19.09.2026

1 первичный балл
≈ 6 мин на практику
3 примера

Ответ: Целое число

Что проверяет задание

В проекте 2027 года здесь анализируют алгоритмы. Для счёта программ удобно вычислять число способов попасть в каждое состояние.

Как решать

Определите команды и допустимые состояния.
Задайте стартовое число способов: один путь в начальную точку.
Суммируйте способы из предшественников; запрещённым состояниям присвойте ноль.

Попробуйте на примере

Авторские учебные примеры. Упражнения показывают отдельный приём; на экзамене условия могут быть сложнее.

Упражнение 1 · Подсчёт программ исполнителя

Исполнитель умеет прибавлять 1 и умножать на 2. Сколько программ переводят число 1 в 5? Разные последовательности команд считаются разными программами.

Показать решение и ответ

f(1) = 1. Для чётного n складываем f(n − 1) и f(n / 2).
f(2) = 2, f(3) = 2, f(4) = 4, f(5) = 4.
У числа 2 два пути из 1: разные команды учитываются отдельно.

Ответ4

Упражнение 2 · Обязательная промежуточная команда

Исполнитель прибавляет 1 или умножает число на 2. Сколько программ ведут из 1 в 6 и проходят через 3?

Показать решение и ответ

Из 1 в 3 есть две программы: +1,+1 и ×2,+1. Совпадающие значения не делают команды одинаковыми.
Из 3 в 6 тоже два пути: три прибавления или умножение на 2. Получаем 2 · 2 = 4.

Ответ4

Упражнение 3 · Запрещённое значение

Исполнитель прибавляет 1 или 2. Сколько программ ведут из 1 в 6, не попадая в 4?

Показать решение и ответ

Число путей до 1 равно 1. До 2 — 1, до 3 — 2, до запрещённого 4 — 0.
До 5 можно прийти только из 3: 2 пути. До 6 — из 5 или 4: 2 + 0 = 2.

Ответ2

Где легко ошибиться

Запрещённое состояние осталось в динамике

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

Складывать участки пути

Если путь обязан пройти через промежуточное значение, число способов на участках перемножают.

Один переход — одна программа

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

Частые вопросы

Можно перемножить числа способов?

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

Закрепите знания на практике

В Репе — короткие уроки, проверка ответа и помощь Помогашки.

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

Смежные задания

Об источниках и редакции

Нумерация, форматы ответов и баллы сверены с опубликованными проектами ФИПИ на 2027 год. Примеры авторские: часть показывает формат задания, часть тренирует отдельный приём. Указанное время — учебный ориентир, а не норматив ФИПИ. После утверждения документов нужна повторная сверка.

Источники: ФИПИ: демоверсии, спецификации, кодификаторы · ФИПИ: планируемые изменения ЕГЭ-2027 · Комплект проекта по предмету (архив)

Сверка содержания: 19 сентября 2026. Статус документов — проект.

Обновлено 2026-09-28