Задание 13: считаем программы исполнителя на Python

Задание 13 ЕГЭ: как превратить команды в подсчёт программ

Нужно посчитать разные последовательности команд, переводящие начальное число в конечное. Мы не выписываем все длинные программы: функция f считает, сколько продолжений есть из текущего состояния.

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

f(x, y) возвращает количество программ из x в y

Число 1 при достижении цели — не значение на экране и не число выполненных команд. Это одна завершённая программа. Если вернуть 0, она исчезнет из суммы и весь подсчёт обнулится.

Проверка запрета стоит перед проверкой x == y. Поэтому даже достижение запрещённого конечного состояния не даст допустимого пути.

Из 2 в 39, не попадая в 14

1. Переносим команды в вызовы

Второй аргумент y остаётся тем же: после каждой команды цель не меняется. Между вызовами ставим +, потому что это варианты выбора следующей команды.

2. Выбираем две причины вернуть ноль

if x > y or x == 14:
    return 0

x > y отсекает перелёт, x == 14 — запрет из условия. Здесь нужен or: достаточно любой причины. Значение x = 39 ещё не является перелётом, поэтому сравнение строгое.

3. Собираем полную программу

def f(x, y):
    if x > y or x == 14:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)

print(f(2, 39))

Как складывается первый шаг

Из 2 получаем 3, 4 или 6. Значит f(2, 39) = f(3, 39) + f(4, 39) + f(6, 39). Запрет 14 действует внутри каждого вызова, а не только на первом шаге.

Из 19 в 3 через 12, без числа 9

1. Меняем направление остановки и команды

Для целой части деления используем //: например, 19 // 2 = 9. Обычное / дало бы 9.5 и не выполнило бы команду из условия.

2. Разбиваем путь по обязательному числу

Для первого отрезка цель y равна 12: если команда перепрыгнула с числа выше 12 сразу ниже 12, вернуться уже нельзя. Такой путь правильно получает 0.

3. Умножаем количества двух частей

def f(x, y):
    if x < y or x == 9:
        return 0
    if x == y:
        return 1
    return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)

print(f(19, 12) * f(12, 3))

Программ из 19 в 12 без 9 — 9, а из 12 в 3 без 9 — 17. Любую первую часть можно продолжить любой второй: 9 × 17 = 153. Оба вызова используют одну функцию с запретом 9.

Внутри f складываем, между обязательными этапами умножаем

Если нужно обязательно пройти два числа в порядке движения, например 6, затем 18, при увеличении от 2 к 24 получится f(2, 6) * f(6, 18) * f(18, 24). Промежуточные числа должны располагаться в достижимом порядке; запреты по-прежнему проверяются внутри f.

Почему каждая ветка вносит своё количество

В маленьких примерах можно увидеть все допустимые программы. Выбери пример: таблица покажет результат каждой первой команды и количество продолжений из него. Ниже перечислены сами программы A, B, C и числа на их пути.

Как ускорить повторные вычисления

Одно и то же f(x, y) может встречаться во многих ветках. Чтобы не считать его заново, можно добавить импорт и декоратор @lru_cache(maxsize=None) прямо над определением функции:

from functools import lru_cache

@lru_cache(maxsize=None)
def f(x, y):
    if x < y or x == 9:
        return 0
    if x == y:
        return 1
    return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)

print(f(19, 12) * f(12, 3))

Ответ остаётся 153. Кеш хранит количество продолжений, поэтому одинаковые результаты разных команд всё равно складываются столько раз, сколько команд их дают.

О кешировании: документация Python.

Собери три программы и проверь их вывод

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

Кнопка «Проверить строки» сравнивает фрагменты с шаблоном. Страница не исполняет введённый Python. Другие способы проверяй запуском в своём редакторе и по числовому ответу. Пробелы между частями выражения и обычные одинарные или двойные кавычки допустимы.

Решено: 0 из 12

def f(x, y):
    if ⟦1⟧ or x == ⟦2⟧:
        return 0
    if x == y:
        return 1
    return f(⟦3⟧, y) + f(⟦4⟧, y) + f(⟦5⟧, y)

print(⟦6⟧)

def f(x, y):
    if ⟦1⟧ or x == ⟦2⟧:
        return 0
    if x == y:
        return 1
    return f(⟦3⟧, y) + f(⟦4⟧, y) + f(⟦5⟧, y)

print(⟦6⟧)

def f(x, y):
    if ⟦1⟧ or x == ⟦2⟧:
        return 0
    if x == y:
        return 1
    return f(⟦3⟧, y) + f(⟦4⟧, y) + f(⟦5⟧, y)

print(⟦6⟧)

Ещё девять вопросов по коду

Ответы можно исправлять и проверять снова.

Скачать Python и задания для самостоятельного решения

Если ответ не совпадает

Вопросы по решению кодом