Навигация по странице
Тип 3
В двух прошлых статьях мы разобрали 23 задания первого и второго типов. Научились писать программы, которые подсчитывают количество способов преобразовать одно число в другое с учётом двух ограничений:
- Когда траектория вычисления не должна содержать какое-то число
- И когда траектория обязательно должна проходить через заданное число
А третий тип этих заданий является не чем иным, как объединением первых двух типов. То есть нам будут даны сразу оба числа, а траектория вычислений должна избегать одно из них и содержать второе. Причем сразу отметим, что таких заданий подавляющее большинство в ЕГЭ по информатике.
Следовательно, для решения 23 заданий третьего типа мы просто объединяем два уже известных нам метода. Если сказано, что траектория не должна содержать число N, то достаточно в блоке условия, который возвращает 0 потребовать равенства переменной x этому числу N:
if x > y or x==N:
return 0
И наоборот, если требуется, чтобы траектория содержала число M, то мы «разбиваем» вычисления функции на два этапа:
f(x, M) * f(M, y)
Вот и всё, ничего более. Давайте убедимся в этом на следующих четырёх примерах.
Пример 1
Начнём с разбора такого задания:
Задание 2322
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Сколько существует программ, для которых при исходном числе 3 результатом является число 20, при этом траектория вычислений содержит число 7 и не содержит 10?»
Давайте разложим всё по полочкам:
- Начальное число (x) у нас 3
- Конечное число (y) — 20
- Траектория не должна содержать (N) число 10
- И должна содержать (M) число 7
Теперь укажем это в коде. Первый блок условия всегда одинаковый:
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 до конечного и перемножить результаты этих вызовов:
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.
Пример 2
Теперь рассмотрим задание с «обратной» траекторией:
Задание 2319
«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Найди целую часть от деления на 2
Сколько существует программ, для которых при исходном числе 60 результатом является число 1, и при этом траектория вычислений содержит число 20 и не содержит 4?»
Поскольку теперь мы движемся «сверху вниз», то есть на уменьшение числа, то нужно поменять местами знаки «меньше» и «больше».
Если 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)
И выведем результат произведения двух функций:
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, которое и запишем в ответ.
Пример 3
И снова пример с траекторией на возрастание:
Задание 2317
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Сколько существует программ, для которых при исходном числе 3 результатом является число 18, при этом траектория вычислений содержит число 14 и не содержит 8?»
Тут уже обойдёмся без подробностей. Исключаем из траектории число 8, применяем все три команды и собираем ответ из произведения двух функций: от 3 до 14 и от 14 до 18.
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.
Пример 4
И последний пример задания этого типа:
Задание 2323
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13.»
Здесь нам уже всё знакомо, только не забываем про знаки «<» и «>», ведь двигаться будем на убывание:
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.