Алгоритм решения задания 13. Часть 1

О задании

В прошлой статье мы познакомились с динамическим программированием и научились находить количество способов преобразовать одно число в другое.

Эти знания пригодятся нам для решения задания 13 ЕГЭ по информатике. В таких заданиях представлен исполнитель с заданным набором команд — как правило, это арифметические действия: сложение, умножение, извлечение корня и другие.

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

В траекторию входят и начальное, и конечное числа. Например, программа «умножить на 2, прибавить 3» для старта 2 создаёт траекторию 2 → 4 → 7. Сами команды здесь важны не меньше результата: другая последовательность может привести к той же цели.

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

Слово «алгоритм» связано с именем средневекового учёного аль-Хорезми. За много веков смысл стал шире, но идея осталась прежней: точная последовательность действий должна приводить к однозначному результату.

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

Кроме того, на траекторию накладываются ограничения. Здесь стоит рассмотреть типы заданий 13:

1. Первый тип: траектория не должна содержать определённое число.
2. Второй тип: траектория обязательно должна содержать определённое число.
3. Третий тип: траектория должна содержать одно число и не содержать другое.
4. Четвёртый тип: ограничения накладываются на количество команд. Задачи этого типа пока что не встречались на реальном экзамене и являются авторскими. Так что отдельно разбирать их мы не будем.

Сейчас же мы вспомним код из предыдущей статьи и научимся решать задания первого типа.

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

Алгоритм решения

Начнём с небольшой ретроспективы. Ранее мы искали количество способов преобразовать число 1 в 8, используя две команды:

1. Прибавить 3
2. Умножить на 2

Для решения мы написали такую функцию:

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

Здесь x — начальное число (1), y — конечное (8). В коде реализованы два базовых случая и рекуррентное соотношение:

1. Базовый случай 1 (x == y): мы достигли цели — функция возвращает 1.
2. Базовый случай 2 (x > y): мы «перескочили» нужное число — этот путь не ведёт к цели, возвращаем 0.
3. Рекуррентное соотношение (x < y): применяем к x каждое действие и суммируем результаты: f(x + 3, y) + f(x * 2, y).

Почему именно сумма — мы разбирали ранее.

Итак, функция проверяет все возможные пути изменения числа. Например, при двукратном вызове f(x + 3, y) траектория будет такой: 1 → 4 → 7.

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

Логично добавить это ограничение ко второму базовому случаю: как траектория с «перескоком» нас не устраивает, также не подходит и траектория с запрещённым числом.

Следовательно, в нашей задаче мы бы изменили код таким образом:

def f(x, y):
    if x == y:
        return 1

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

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

Таким образом, у нас теперь есть два случая, когда траектория нам не подходит и функция должна возвращать 0:

1. Если число х оказывается больше конечного
2. Если число х является запрещённым

Посмотрим, что произошло с нашими тремя маршрутами из 1 в 8. Пути 1 → 4 → 8 и 1 → 2 → 4 → 8 содержат четвёрку, поэтому исчезают. Остаётся только траектория 1 → 2 → 5 → 8.

Важно: функция не пытается «перепрыгнуть» запрещённую точку и продолжить путь. Как только x стало равно 4, она возвращает 0. Этот ноль поднимается вверх по рекурсивной ветви и сообщает: подходящих продолжений здесь нет.

Поэтому запрещённое число проверяют в базовом случае. Базовый случай — это не просто конец вычислений, а правило, которое присваивает всей завершившейся ветви вклад 1 или 0.

Не спешите сразу печатать функцию. Сначала выпишите четыре вещи: старт, финиш, команды и запрещённые значения. Затем определите, увеличивают команды число или уменьшают его.

Направление нужно для проверки перескока. При движении вверх ветвь обрывается, когда x > y. При движении вниз — когда x < y. Сравнение зависит от команд, а не от привычки писать один и тот же знак.

Пример 1

Давайте теперь на практике проверим данную логику. Рассмотрим задание с такой формулировкой:

№ 13002. Демоверсия Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя…

Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.

Открыть задание

Начало у функции будет всегда одинаковым:

def f(x, y):
    if x == y:
        return 1

Далее нам необходимо определить два условия базового случая:

1. Когда x > y
2. Когда x = 11

def f(x, y):
    if x == y:
        return 1

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

Теперь, если x всё ещё меньше y будем вызывать функцию f с каждой из заданных команд:

def f(x, y):
    if x == y:
        return 1

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

    if x < y:
        return f(x + 1, y) + f(x * 2, y) + f(x ** 2, y)

Осталось лишь добавить вывод на экран результата работы функции с аргументами 2 и 20:

def f(x, y):
    if x == y:
        return 1

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

    if x < y:
        return f(x + 1, y) + f(x * 2, y) + f(x ** 2, y)


print(f(2, 20))

В результате получаем число 37.

Почему возведение в квадрат не требует отдельной логики? Для функции это всего лишь ещё одна стрелка из состояния x. Если x² перескочит 20, следующий вызов попадёт в базовый случай x > y и вернёт 0.

Зачем нужен кеш

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

В нашем примере число 4 можно получить сразу несколькими способами: прибавить к 2 единицу два раза, умножить 2 на 2 или возвести 2 в квадрат. После этого во всех случаях нужно решить одну задачу: сколько подходящих путей ведёт из 4 в 20?

Без кеша каждый вызов f(4, 20) заново строит всё дерево продолжений от 4 до 20. Программа снова проверяет те же числа, выполняет те же команды и получает тот же ответ. Чем длиннее траектории, тем больше становится такой повторной работы.

Кеш — это память о уже выполненных вызовах функции. Удобно представить его как таблицу: слева записаны аргументы функции, а справа — вычисленный для них результат. Для нашего примера одной из записей станет пара «(4, 20) → количество путей».

Когда f(4, 20) вызывается впервые, готовой записи ещё нет. Функция выполняет рекурсивные вычисления, получает ответ и сохраняет его в кеше. Такой первый вызов называют промахом кеша: значение пришлось вычислить.

Когда программа снова встречает f(4, 20), она находит сохранённый ответ и сразу возвращает его. Рекурсивное дерево второй раз не строится. Это уже попадание в кеш: результат удалось взять из памяти.

Важно, что кеш не склеивает разные программы исполнителя и не уменьшает ответ. Каждая ветвь всё равно получает количество продолжений из числа 4 и прибавляет его к своей сумме. Мы экономим вычисления, но считаем все траектории.

В Python готовый кеш для функций находится в модуле functools. Подключим из него lru_cache и поставим строку @lru_cache(None) непосредственно перед определением f:

from functools import lru_cache

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1

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

    if x < y:
        return f(x + 1, y) + f(x * 2, y) + f(x ** 2, y)

print(f(2, 20))

Строка со знаком @ называется декоратором. Декоратор позволяет изменить поведение функции, не переписывая её тело. lru_cache оборачивает f: перед обычным вычислением он проверяет, нет ли ответа для этих аргументов в кеше.

Имя LRU расшифровывается как Least Recently Used — «давно не использовавшийся». Если размер кеша ограничен, декоратор освобождает место, удаляя записи, к которым дольше всего не обращались.

В записи @lru_cache(None) значение None означает, что мы не задаём предел количества записей. Для задач ЕГЭ это удобно: возможных чисел немного, поэтому все найденные ответы можно хранить до конца работы программы.

После добавления декоратора имя f обозначает уже не исходную функцию, а её обёрнутую версию с кешем. Поэтому и первый вызов f(2, 20), и все рекурсивные вызовы внутри функции проходят через одну и ту же проверку памяти.

Ключом кеша становятся все аргументы вызова. Здесь это x и y, поэтому f(4, 20) и f(4, 30) считаются разными задачами. Числа подходят для ключей, поскольку их значение не меняется после создания.

Кеширование безопасно, когда одинаковые аргументы всегда дают одинаковый результат. Наша f именно такая: при неизменных командах и запрещённых числах ответ зависит только от текущего x и цели y.

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

В маленьком примере программа справится и без кеша, поэтому ответ останется тем же — 37. Разница заметна на больших числах: с lru_cache каждая задача вида «сколько путей ведёт из x в цель» решается один раз, а все следующие обращения получают готовый ответ.

Пример 2

Рассмотрим ещё одно задание:

В этом задании нам необходимо добавить сразу два числа в условие. Но сложностей в этом нет никаких, просто также через оператор or проверяем равенство переменной x числам 9 и 16.

И ещё один момент: раньше мы всегда двигались по возрастанию: исходное число было меньше конечного. Здесь же обратная ситуация. Следовательно, все знаки сравнения (< и >) нам следует поменять на обратные!

Таким образом, если наше проверяемое число x будет либо меньше конечного (3), либо по траектории вычисления примет значения 9 или 16, то будет возвращаться 0. Это будет означать, что данная траектория вычислений нам не подходит.

А продолжать рекурсивно вызывать функцию f мы будем только, если переменная x больше конечного числа (y).

В остальном – без изменений. Код будет таким:

def f(x, y):
    if x == y:
        return 1

    if x < y or x == 9 or x == 16:
        return 0

    if x > y:
        return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)


print(f(19, 3))

В конце работы программы получаем число 180.

Обратите внимание на целочисленное деление: 10 // 3 равно 3, а не 3,333… Команда сразу переводит исполнителя в целое состояние. Если результат окажется ниже цели, проверка x < y отсеет ветвь.

Пример 3

В заключение рассмотрим задание с такой формулировкой:

№ 13200. Авторская задача Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Умножить на 3 С. Умножить на 5 Программа для исполнителя…

Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 3
С. Умножить на 5

Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 90, при этом траектория вычислений не содержит чисел 18 и 30 ?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы СBA при исходном числе 2 траектория будет состоять из чисел 10, 30, 31.

Открыть задание

Снова работаем с двумя числами и движемся «вверх».

И решается данное задание следующим образом:

def f(x, y):
    if x == y:
        return 1

    if x > y or x == 18 or x == 30:
        return 0

    if x < y:
        return (f(x + 1, y) + f(x * 3, y) + f(x * 5, y))


print(f(2, 90))

В результате получаем число 145, которое и запишем в ответ.

Здесь удобно хранить запрещённые значения в множестве {18, 30}. Тогда проверка читается почти как условие задачи: если текущее число находится среди запрещённых, этот путь не учитываем.

FORBIDDEN = {18, 30}

def f(x, y):
    if x == y:
        return 1

    if x > y or x in FORBIDDEN:
        return 0

    if x < y:
        return (f(x + 1, y) + f(x * 3, y) + f(x * 5, y))


print(f(2, 90))

Итоги

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

Сначала определите направление движения. Если все команды увеличивают число, перескок проверяется условием x > y. Если уменьшают — условием x < y. После этого примените каждую команду и сложите ответы ветвей.

Шаблон для возрастающей траектории:

from functools import lru_cache

FORBIDDEN = {*1}

@lru_cache(None)
def f(x, target):
    if x in FORBIDDEN:
        return 0
    if x == target:
        return 1
    if x > target:
        return 0
    return f(*2, target) + f(*3, target)

print(f(*4, *5))

В шаблоне lru_cache выполняет ту же работу: запоминает результат для каждой пары (x, target). Убирать декоратор не обязательно — он не меняет логику подсчёта, а только избавляет программу от повторного обхода одинаковых продолжений.

Обозначения здесь такие:

• *1 — запрещённые числа через запятую;
• *2 и *3 — выражения для команд;
• *4 — начальное число;
• *5 — конечное. Если команд больше двух, добавьте ещё слагаемые.

Для убывающей траектории меняется только проверка перескока: используйте if x < target. Сами команды записывайте так, как они даны в условии: x - 1, x // 3 и так далее.

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

В следующей статье рассмотрим обратное ограничение: траектория должна будет обязательно пройти через заданное число.