Задание 13 ЕГЭ по информатике: количество программ исполнителя

Задание 13 ЕГЭ по информатике в 2027 году проверяет умение анализировать ход исполнения алгоритма: нужно посчитать, сколько существует программ, которые переводят одно число в другое. Решают его таблицей, в которой для каждого промежуточного числа записано количество способов до него дойти.

Как решать

Исполнитель меняет число на экране командами, и в этом задании каждая команда увеличивает число. Поэтому программа не может зациклиться, и количество программ можно считать по порядку: число программ, которые приводят в число x, равно сумме таких чисел для всех значений, из которых x получается одной командой.

Выпишите в строку числа от исходного до конечного и поставьте под исходным числом 1. Двигайтесь слева направо и прибавляйте значение каждого числа ко всем числам, в которые из него ведут команды. Для команды «Прибавь 1» это следующее число, для «Умножь на 2» — удвоенное, для команд, которые работают с цифрами, — число, которое получится по правилу команды.

Условия на траекторию делят задачу на части. Если траектория должна содержать число m, посчитайте программы от исходного числа до m и от m до конечного и перемножьте результаты. Если траектория не должна содержать число k, поставьте под k ноль и не передавайте из него значения дальше.

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

На Python тот же расчёт записывается функцией count(x, y) с запоминанием результатов через lru_cache: она возвращает 1, если x равно y, 0 при перелёте или запрещённом числе и сумму вызовов для всех применимых команд в остальных случаях.

Примеры с решением

Пример 1

Исполнитель преобразует число на экране. У исполнителя есть три команды:

Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Сколько существует программ, для которых при исходном числе 3 результатом является число 22, при этом траектория вычислений содержит число 10 и не содержит числа 17?

Проверка ответа на Python

from functools import lru_cache


@lru_cache(None)
def count(x, y):
    """Число программ, переводящих x в y (команды только увеличивают число)."""
    if x == y:
        return 1
    if x > y or x == 17:          # перелёт или запрещённое число
        return 0
    return count(x + 1, y) + count(x + 2, y) + count(x * 2, y)


print(count(3, 10) * count(10, 22))

Ответ: 2040

Разделим путь на две части. От 3 до 10 таблица даёт 30 программ: число 17 здесь не встречается. От 10 до 22 нужно поставить ноль под числом 17 и не передавать из него значения; получается 68 программ. Любую программу первой части можно продолжить любой программой второй, поэтому ответ равен 30 × 68 = 2040.

Пример 2

Исполнитель преобразует число на экране. У исполнителя есть две команды:

Команда B применяется только к числу, у которого цифра в разряде единиц от 1 до 4, и заменяет эту цифру удвоенной, остальные цифры не меняются. Например, из 23 получается 26, а к числу 25 команда B неприменима.

Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Сколько существует программ, для которых при исходном числе 21 результатом является число 58, при этом траектория вычислений содержит число 44 и не содержит числа 36?

Проверка ответа на Python

from functools import lru_cache


def double_units(x):
    """Команда B: применима, если цифра единиц от 1 до 4; эта цифра удваивается."""
    d = x % 10
    return x + d if 1 <= d <= 4 else None


@lru_cache(None)
def count(x, y):
    if x == y:
        return 1
    if x > y or x == 36:             # перелёт или запрещённое число
        return 0
    total = count(x + 1, y)
    b = double_units(x)
    if b is not None:
        total += count(b, y)
    return total


print(count(21, 44) * count(44, 58))

Ответ: 3200

Команда B прибавляет к числу его последнюю цифру, если она от 1 до 4, поэтому числа только растут. От 21 до 44 с запретом числа 36 получается 160 программ, от 44 до 58 — 20 программ. Ответ: 160 × 20 = 3200.

Типичные ошибки

Потренироваться на тренажёре

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

Почему задание 13 в 2027 году стало про количество программ?

В проекте спецификации 2027 года тематику «Умение анализировать ход исполнения алгоритма» перенесли из задания 23 в задание 13. Задание про маску подсети теперь стоит под номером 10.

Можно ли решать задание 13 на Python?

Можно: на экзамене есть среды программирования. Функция с запоминанием из примеров считает ответ за доли секунды, а таблица на бумаге помогает не ошибиться в условиях на траекторию.

Как проверить ответ без компьютера?

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

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 12 и задание 14.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.