В двух прошлых статьях мы разобрали первый и второй типы задания 13. Научились писать программы, которые подсчитывают количество способов преобразовать одно число в другое с учётом двух ограничений:
Когда траектория вычисления не должна содержать какое-то число
И когда траектория обязательно должна проходить через заданное число
А третий тип этих заданий является не чем иным, как объединением первых двух типов. То есть нам будут даны сразу оба числа, а траектория вычислений должна избегать одного из них и содержать второе. Такой смешанный вариант особенно часто встречается в тренировочных наборах ЕГЭ по информатике.
Представьте маршрут с двумя условиями: нужно обязательно заехать в один город, но объехать другой из-за закрытой дороги. Условия действуют одновременно, однако отвечают на разные вопросы и потому обрабатываются по-разному.
Обязательная точка делит маршрут на участки. Запрещённая точка, напротив, закрывает любую ветвь, которая в неё попала. Одно ограничение собирает ответ, другое фильтрует неподходящие варианты.
Так устроены и многие настоящие алгоритмы поиска пути: сначала задаются контрольные пункты, затем исключаются недоступные состояния. Экзаменационная задача показывает эту большую идею на маленькой числовой модели.
Алгоритм решения
Для решения задач третьего типа задания 13 мы просто объединяем два уже известных нам метода. Если сказано, что траектория не должна содержать число N, то достаточно добавить к базовым случаям проверку: при равенстве x этому числу N функция возвращает 0:
if x > y or x == N:
return 0
Если таких чисел несколько (здесь – N и M), то можно воспользоваться множеством и оператором принадлежности:
if x > y or x in {N, M}:
return 0
В примерах мы будем объединять оба условия: проверку перескока (x > yздесь) и проверку запрещённого числа (x == N). Но вы можете их и разделить: сначала проверять запрещённые числа, потом писать условие достижения цели (x == N), а затем проверку перескока. Такой вариант программы будет предложен в конце в виде шаблона.
Если требуется, чтобы траектория содержала число M, то мы «разбиваем» вычисления функции на два (и более) этапа:
f(x, M) * f(M, y)
На уровне идеи это всё. Но прежде чем переходить к примерам, соберём действия в понятный порядок, чтобы два ограничения не смешались в одну случайную строку кода.
Шаг 1. Выпишите старт, финиш, обязательное и запрещённое значения. Для нескольких обязательных точек сразу расположите их в том порядке, в котором их можно достичь.
Шаг 2. Определите направление команд. При увеличении чисел перескок — это x > y, при уменьшении — x < y.
Шаг 3. Внутри функции сначала отбрасывайте запрещённые значения, затем проверяйте достижение цели и перескок. После базовых случаев применяйте все команды из условия.
Шаг 4. Вне функции разделите траекторию в обязательной точке и перемножьте ответы для участков. Запрещённое условие автоматически подействует на каждый участок, потому что оба вызова используют одну функцию.
Зачем здесь кеширование
Декоратор lru_cache мы уже подробно разбирали во второй статье. Там выяснили, что кеш запоминает результат функции для каждого набора аргументов и возвращает готовый ответ, если тот же вызов встречается снова.
В прошлой статье мы обошлись без кеширования: числа в примерах были небольшими, поэтому программа успевала выполнить все вычисления напрямую. Так код было проще читать во время первого знакомства со вторым типом задания.
Здесь значения становятся больше, а разные последовательности команд чаще приводят к одному промежуточному числу. Без кеша функция заново обходит одинаковые продолжения. lru_cache сохраняет их ответы и заметно ускоряет работу.
Поэтому в каждом полном решении подключим lru_cache из модуля functools и поставим декоратор @lru_cache(None) перед функцией. В промежуточных фрагментах эти две строки повторять не будем: там мы по шагам собираем только основную логику.
Почему ограничения не мешают друг другу
Допустим, путь обязан пройти через 7 и не должен проходить через 10. Выражение f(x, 7) * f(7, y) строит только маршруты через 7, а проверка x == 10 удаляет из обоих множителей ветви с десяткой.
Получается аккуратное разделение обязанностей: произведение отвечает за «обязательно пройти», а возвращаемый ноль в базовом случае x == 10 — за «ни в коем случае не заходить».
Пример 1
Начнём с разбора такого задания:
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1 B. Умножить на 2 C. Возвести в квадрат
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
Теперь укажем это в коде. Первый блок условия всегда одинаковый:
def f(x, y):
if x == y:
return 1
В следующем блоке указываем число, которого не должно быть в траектории (N):
def f(x, y):
if x == y:
return 1
if x > y or x == 10:
return 0
Далее, пока x < y, то есть пока мы не дошли до нужного числа, применяем все три действия к переменной x:
def f(x, y):
if x == y:
return 1
if x > y or x == 10:
return 0
if x < y:
return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)
Осталось лишь вызвать эту функцию от исходного числа до числа M, от числа M до конечного и перемножить результаты этих вызовов: В полном решении также подключаем кеширование, чтобы одинаковые рекурсивные вызовы не вычислялись заново.
from functools import lru_cache
@lru_cache(None)
def f(x, y):
if x == y:
return 1
if x > y or x == 10:
return 0
if x < y:
return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)
print(f(3, 7) * f(7, 20))
Запускаем нашу программу и получаем ответ на это задание — число 792.
Прочитаем итоговый вызов словами: выбираем любой допустимый путь из 3 в 7 и соединяем его с любым допустимым путём из 7 в 20. Если на любом участке встречается 10, соответствующая ветвь даёт 0 и в ответ не попадает.
Пример 2
Теперь рассмотрим задание с «обратной» траекторией:
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 60 результатом является число 1, и при этом траектория вычислений содержит число 20 и не содержит 4?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Поскольку теперь мы движемся «сверху вниз», то есть на уменьшение числа, то нужно поменять местами знаки «меньше» и «больше».
Если x меньше y или равен 4, то функция должна возвращать 0:
def f(x, y):
if x == y:
return 1
if x < y or x == 4:
return 0
А пока x больше y, будем применять к нему действия из условия:
def f(x, y):
if x == y:
return 1
if x < y or x == 4:
return 0
if x > y:
return f(x - 1, y) + f(x // 2, y)
И выведем результат произведения двух функций:
from functools import lru_cache
@lru_cache(None)
def f(x, y):
if x == y:
return 1
if x < y or x == 4:
return 0
if x > y:
return (f(x - 1, y) + f(x // 2, y))
print(f(60, 20) * f(20, 1))
Запустив программу, получим число 1760, которое и запишем в ответ.
Здесь особенно важно не перенести знак из предыдущего примера автоматически. Команды уменьшают число, поэтому именно x < y означает, что цель уже перескочили.
Пример 3
И снова пример с траекторией на возрастание:
Исполнитель преобразует число на экране. У исполнителя есть три команды, которым обозначены латинскими буквами:
A. Прибавить 1 B. Умножить на 2 C. Умножить на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 25, и при этом траектория вычислений содержит число 15, но не содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы CBAпри исходном числе 3 траектория состоит из чисел 9, 18, 19.
Тут уже обойдёмся без подробностей. Исключаем из траектории число 8, применяем все три команды и собираем ответ из произведения двух функций: от 3 до 14 и от 14 до 18.
from functools import lru_cache
@lru_cache(None)
def f(x, y):
if x == y:
return 1
if x > y or x == 8:
return 0
if x < y:
return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)
print(f(3, 14) * f(14, 18))
Запускаем программу и получаем ответ на это задание — 360.
Хотя число 8 меньше обязательной точки 14, запрет всё равно проверяется на каждом вызове. Это защищает первый участок 3 → 14; на втором участке 14 → 18 попасть в 8 уже невозможно из-за возрастающих команд.
Пример 4
И последний пример задания этого типа:
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Прибавить 1 В. Прибавить 3 С. Возвести в квадрат
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 26, при этом траектория вычислений содержит число 20 и не содержит числа 16?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 4 траектория будет состоять из чисел 16, 19, 20.
Здесь нам уже всё знакомо, только не забываем про знаки «<» и «>», ведь двигаться будем на убывание:
from functools import lru_cache
@lru_cache(None)
def f(x, y):
if x == y:
return 1
if x < y or x == 7:
return 0
if x > y:
return f(x - 1, y) + f(x - 4, y) + f(x // 3, y)
print(f(19, 13) * f(13, 2))
Запускаем программу, получаем ответ, а именно — число 68.
В последнем примере обязательная точка 13 идёт раньше запрещённой 7 по направлению движения. Но запрещать 7 нужно во всей функции: так шаблон остаётся универсальным и не заставляет нас вручную рассуждать, на каком участке опасное число достижимо.
Теперь соберём всё в короткий, но связный итог.
Итоги
В смешанном типе одновременно действуют обязательные и запрещённые точки. Обязательная точка разрезает маршрут на части, а запрещённая превращает любую попавшую в неё ветвь в ноль.
Кеширование не меняет количество найденных программ. Оно лишь сохраняет ответы для уже встречавшихся пар (x, target), поэтому повторный вызов получает готовое значение вместо нового обхода тех же рекурсивных ветвей.
Шаблон решения:
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 *2:
return 0
return f(*3, target) + f(*4, target)
answer = f(START, M) * f(M, FINISH)
print(answer)
Обозначения:
*1 — запрещённые значения;
*2 — проверка перескока;
*3 и *4 — команды;
M — обязательная точка. Для дополнительных команд добавьте слагаемые, для дополнительных обязательных точек — множители.
Всегда обращайте внимание на направление изменения числа, порядок обязательных точек и знаки сравнения. При игре на увеличение перескок проверяется через x > target, при движении на уменьшение — через x < target.
Помните, что проверка запрещённого числа должна возвращать 0 и быть самой первой, либо в блоке с проверкой перескока (как в примерах выше), а достижение цели — 1. Следите, чтобы каждая рекурсивная ветвь действительно приближала текущее число к цели и не могла зациклиться.
На этом мы закончили разбор трёх основных типов задания 13 ЕГЭ по информатике. Попрактиковаться в подсчёте траекторий можно в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
