Задание 13 ЕГЭ по информатике: исполнитель и количество программ — разбор и примеры

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

С 2027 года эта задача (анализ хода исполнения алгоритма) стоит в варианте под номером 13; до этого она была заданием 23.

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

• умение формализовать работу исполнителя: какие числа можно получить из данного за одну команду;
• понимание траектории программы — последовательности всех чисел, появлявшихся на экране, включая начальное и конечное;
• знание метода динамического программирования: число программ, приводящих в x, равно сумме чисел программ, приводящих во все числа, из которых x получается одной командой;
• умение учитывать обязательные и запрещённые точки траектории.

Типичные формулировки

1. «Сколько существует программ, для которых при исходном числе 2 результатом является число 25?»
2. «…и при этом траектория вычислений содержит число 12» — обязательная точка.
3. «…и траектория не содержит числа 18» — запрещённая точка.
4. Исполнители с уменьшающими командами («вычесть 1», «разделить нацело на 2») — тогда идут от большего числа к меньшему.
5. Команды, зависящие от числа: «прибавить следующее чётное», «сделать число нечётным» и т. п.

Пошаговый метод

1. Определите направление. Если все команды увеличивают число, считать удобно от начального к конечному.
2. Разбейте путь обязательными точками. Если траектория должна содержать 12, число программ равно произведению: (программы из начала в 12) × (программы из 12 в конец). Это правило умножения из комбинаторики.
3. Запрещённые точки обнулите. В таблице просто ставим 0 в клетку запрещённого числа; в рекурсии возвращаем 0, если попали в него.
4. Заполните таблицу от начального числа: в клетку начала пишем 1, для каждого следующего x складываем значения клеток, из которых x получается одной командой.
5. Проверьте программой. На экзамене есть компьютер, рекурсия с перебором пишется за минуту и исключает арифметические ошибки.

Разбор примера 1 (вручную, таблицей)

Исполнитель имеет две команды: «прибавить 1» и «умножить на 2». Сколько существует программ, которые преобразуют число 1 в число 10?

Обозначим k(x) — число программ, приводящих из 1 в x. Тогда k(1) = 1, а для x > 1: k(x) = k(x − 1) плюс k(x / 2), если x чётно.

Например, k(8) = k(7) + k(4) = 6 + 4 = 10. Ответ: 14.

Разбор примера 2 (с условиями)

Исполнитель имеет три команды: А — прибавить 1, Б — прибавить 3, В — умножить на 2. Сколько существует программ, которые преобразуют число 2 в число 25, при этом траектория вычислений содержит число 12 и не содержит числа 18?

Разбиваем путь. Ответ = (программы 2 → 12) × (программы 12 → 25 без числа 18). Ограничение «не содержит 18» касается только второго участка, потому что на первом участке числа не превосходят 12.

Первый участок. Заполняем таблицу k(x) = k(x − 1) + k(x − 3) + k(x / 2) от 2 до 12 (слагаемые берём, только если исходное число не меньше 2): получаем k(12) = 61.

Второй участок. Начинаем с k(12) = 1, клетку 18 обнуляем, считаем до 25: получаем 35.

Ответ: 61 · 35 = 2135.

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

Код на Python

Рекурсия перебирает все программы: функция возвращает число программ из a в b, обходя запрещённые числа.

def f(a, b, banned=()):
    if a > b or a in banned:
        return 0
    if a == b:
        return 1
    return f(a + 1, b, banned) + f(a + 3, b, banned) + f(a * 2, b, banned)

print(f(2, 12) * f(12, 25, banned=(18,)))   # 2135

Если числа большие (сотни и тысячи), добавьте @lru_cache(None) из модуля functools над функцией — иначе перебор может работать долго. Можно написать и итеративную динамику в списке cnt, повторяя ручную таблицу:

def dp(a, b, banned=()):
    cnt = [0] * (b + 1)
    cnt[a] = 1
    for x in range(a + 1, b + 1):
        if x in banned:
            continue
        cnt[x] = cnt[x - 1]
        if x - 3 >= a:
            cnt[x] += cnt[x - 3]
        if x % 2 == 0 and x // 2 >= a:
            cnt[x] += cnt[x // 2]
    return cnt[b]

print(dp(2, 12) * dp(12, 25, banned=(18,)))   # 2135

Оба способа дали одинаковый ответ — это хорошая самопроверка.

Исполнители с уменьшающими командами

Если команды уменьшают число («вычесть 2», «разделить нацело на 3»), меняется только направление и условие остановки. В рекурсии проверка a > b заменяется на a < b: число уже меньше цели, и вернуться к ней нельзя. В таблице клетки заполняются от большего числа к меньшему. Отдельно будьте внимательны с делением нацело: из нескольких разных чисел можно получить одно и то же (например, 9, 10 и 11 при делении нацело на 3 дают 3), поэтому при обратном счёте у клетки может оказаться больше «предков», чем при умножении. Программа перебором учитывает это автоматически, а при ручном счёте такие случаи легко пропустить.

Частые ошибки

• Забывают про условие «a > b». Без него рекурсия с увеличивающими командами никогда не остановится.
• Складывают участки вместо умножения. Для обязательной точки число программ — произведение.
• Обнуляют запрещённое число на неправильном участке или забывают, что начальное и конечное числа тоже входят в траекторию.
• Путают «содержит число» и «проходит через команду». Траектория — это числа на экране, а не команды.
• При командах деления считают в неправильном направлении: «разделить нацело на 2» из 7 даёт 3, а не 3,5.
• Учитывают x / 2 для нечётного x в таблице с командой «умножить на 2».

Потренируйтесь

Решите задания № 13 в банке и попробуйте задачи с проверкой кода, где программу проверяют автотесты. Идея динамики подробно разобрана в статье «Подсчёт путей и динамическое программирование». Следующее задание — задание 14: системы счисления.