Исполнитель ЕГЭ: как посчитать количество программ на Python

Что считается программой и где искать эту тему

У исполнителя есть команды, меняющие число. Программа — последовательность команд, которая переводит начальное число в конечное. Считаем такие последовательности, а не количество промежуточных чисел.

Возьмём положительные числа и две команды: 1) прибавить 1; 2) умножить на 2. Из 2 в 4 можно попасть программой «11»: 2 → 3 → 4, или программой «2»: 2 → 4. Ответ — 2 программы.

В прежней нумерации ЕГЭ это тема задания 23. В плане изменений ФИПИ на 2027 год анализ исполнения алгоритма перенесён в задание 13. На сайте доступны текущая подборка №13 и прежняя №23.

Почему ветки складывают, а в конечной точке пишут 1

Из каждого числа x можно перейти в x + 1 или 2x. Для нашего примера число программ до финиша равно сумме чисел программ из этих двух следующих состояний:

F(x) = F(x + 1) + F(2x)

Если уже пришли в цель, засчитываем 1: одна найденная последовательность завершена, дополнительные команды не нужны. Если превысили цель — 0, потому что обе команды только увеличивают положительное число.

Не ставьте в конечной точке 0: тогда все суммы тоже станут нулевыми. И не переносите проверку «x больше цели» в задачи с вычитанием или делением: там можно вернуться назад, а иногда возникают циклы.

Из 2 в 10: считаем по таблице

Можно двигаться от старта и считать способы добраться до каждого числа. В начале у 2 записываем 1. К числу x приходим из x − 1 командой +1 и, если x чётное, из x/2 командой ×2. Учитываем только достижимые числа от старта.

Например, в 6 приходим из 5 или 3: 2 + 1 = 3 программы. В 10 — из 9 или 5: 5 + 2 = 7. Это и есть ответ для всего примера.

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

Решение рекурсией в Python

from functools import lru_cache

# В примере: положительные числа и только команды +1, *2.
@lru_cache(maxsize=None)
def ways(x, target, blocked=-1):
    if x > target or x == blocked:
        return 0
    if x == target:
        return 1
    return ways(x + 1, target, blocked) + ways(x * 2, target, blocked)

print(ways(2, 10))                    # 7
print(ways(2, 6) * ways(6, 10))       # 3: обязательно через 6
print(ways(2, 10, blocked=5))         # 3: не заходя в 5

Сначала проверяем выход за цель и запрещённое число. Потом — успешное достижение цели. После этого складываем две ветки. Параметр blocked равен −1 по умолчанию: в нашем примере с положительными числами такого состояния не будет.

lru_cache запоминает результаты для сочетания x, target и blocked. Поэтому одинаковые расчёты не выполняются повторно. Для очень длинной цепочки используйте таблицу и цикл из следующего раздела: кеш не устраняет ограничение глубины рекурсии.

Скачать программу с рекурсией и циклом. Сохраните с расширением .py. При последовательном запуске примеры выведут 7, 3, 3, 7.

Обязательное и запрещённое число

Нужно пройти через 6. Разбиваем программу на две части: из 2 в 6 и из 6 в 10. До 6 есть 3 программы, после 6 — одна: +1 четыре раза. Каждую первую часть можно соединить со второй: 3 × 1 = 3 программы.

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

Нельзя заходить в 5. В состоянии 5 сразу возвращаем 0. Для пути из 2 в 10 остаются 3 программы. В таблице это значит: значение для 5 равно нулю и от него ничего не переносим дальше.

То же решение без рекурсии

start, target = 2, 10
count = {x: 0 for x in range(start, target + 1)}
count[start] = 1

for x in range(start, target + 1):
    for next_x in (x + 1, x * 2):
        if next_x <= target:
            count[next_x] += count[x]

print(count[target])  # 7

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

Не объединяйте одинаковые результаты разных команд в set. Если начать с 1, команды +1 и ×2 обе дадут 2, но это две разные однокомандные программы. Цикл по (x + 1, x * 2) правильно прибавит обе.

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

Самопроверка перед экзаменационной задачей

• Не перепутаны число программ и длина кратчайшей программы.
• Каждая допустимая команда даёт отдельную ветку, даже если результаты двух команд совпали.
• У цели стоит 1, у запрещённого состояния — 0.
• Отсечение x > target используется только там, где нельзя вернуться к цели.
• Обязательная точка и запреты учтены во всех частях маршрута.

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

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.