В прошлой статье мы познакомились с типами задания 15 ЕГЭ по информатике, освоили ручное решение первого типа и составили универсальную заготовку для перебора.
Теперь настало время двигаться дальше и разобрать второй тип. Здесь, как уже говорилось ранее, нам предстоит поработать с некоторыми необычными функциями, работу которых мы будем либо имитировать на бумаге, либо воссоздавать в коде.
Необычное имя не означает новый вид логики. ДЕЛ, ТРЕУГ и МАКС — всего лишь короткие обозначения для обычных условий. Сначала переводим имя на понятный язык, а потом работаем с формулой как раньше.
В программировании функцию, которая отвечает «да» или «нет», часто называют предикатом. Например, ДЕЛ(x, 9) — предикат: он истинен для 9, 18, 27 и ложен для 10 или 20.
Далее рассмотрим одно ручное решение и на двух примерах вспомним программный метод и адаптируем его под новый тип.
Сразу рассмотрим вот такую формулировку 15 задания:
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа A логическое выражение (ДЕЛ(x, 9) → ¬ ДЕЛ(x, 6)) ∨ (x + A ≥ 100) истинно (т.е. принимает значение 1) при любом целом положительном значении переменной x?
Давайте рассуждать. В выражении мы имеем импликацию ДЕЛ(x, 9) → ¬ ДЕЛ(x, 6). И дизъюнкцию результата импликации с выражением x + A ≥ 100.
Нам нужно определить, в каких ситуациях все выражение будет ложным, а затем, на основе этих данных, подобрать значения для неизвестного числа А. Начнём с импликации.
Импликация ложна только в одном случае: слева истина, а справа ложь. Во всех остальных случаях она истинна:
Нас интересует здесь только последний случай. Иными словами, число x должно делиться на 9 без остатка (истинность ДЕЛ(x, 9)) и вместе с этим должно делиться на 6 (ложность ¬ ДЕЛ(x, 6))
Значит, нам нужно рассмотреть только те случаи, когда значение x кратно и 9, и 6 — это будет число 18 и все кратные ему (число 18 — это наименьшее общее кратное 6 и 9).
Почему появляется именно 18? Разложим числа: 9 = 3², а 6 = 2 · 3. Чтобы число делилось на оба, в нём должны встретиться множители 2 и 3². Их произведение равно 18.
Дальше подходят 36, 54, 72 и так далее. Но для неравенства x + A ≥ 100 самым опасным будет наименьший x: чем меньше x, тем больше A требуется для компенсации.
Теперь переходим ко второй части — дизъюнкции. Дизъюнкция будет ложной тогда и только тогда, когда оба операнда будут ложны одновременно. То есть, когда выражение будет возвращать ложь, в то время, когда импликация тоже ложна, все логическое выражение будет ложно.
Вторая часть дизъюнкции ложна, когда x + A < 100, то есть A < 100 − x. При таких A всё выражение может стать ложным.
Но вернёмся к x. Ранее мы уже определили, что он может принимать значения, кратные 18. Максимальное же значение A мы получим при минимальном значении x — то есть, когда x будет равен 18. Отсюда вычисляем A:
A < 100 – 18
⇒ A < 82.
Таким образом, мы установили, что при значениях A, меньших 82, выражение x + A ≥ 100 будет ложным, что, в свою очередь, повлечёт за собой ложность всего логического выражения (при x = 18):
Отсюда делаем вывод, что значение A должно быть не менее 82 (A ≥ 82), тогда второй операнд в дизъюнкции будет истинным и все выражение также истинным. Ну а наименьшим значением тут будет число 82. Его и записываем в ответ.
Проверяем границу. При A = 81 и x = 18 обе части дизъюнкции ложны, поэтому 81 не подходит. При A = 82 вторая часть равна 18 + 82 ≥ 100 и становится истинной.
Для всех следующих кратных 18 значение x только увеличивается, а значит, неравенство x + A ≥ 100 уже тем более выполняется. Так мы проверили не одну точку, а сразу всю последовательность.
Как переводить именованные функции?
Начинайте с отдельного словаря-переводчика. ДЕЛ(n, m) означает, что остаток n % m равен нулю. Отрицание ДЕЛ означает, что остаток не равен нулю.
ТРЕУГ(n, m, k) требует трёх строгих неравенств треугольника. МАКС(a, b) уже существует в Python под именем max, поэтому писать для неё свою функцию не нужно.
Лишь после такого перевода записывайте большую формулу. Если переписывать всё одним движением, легко потерять отрицание или поставить его не перед той частью.
Что же, алгоритм ручного решения рассмотрели. Все действия идентичны плану, который мы вывели еще в прошлой статье. Так что теперь перейдём к программному решению второго типа 15 заданий.
На очереди у нас такое задание:
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А логическое выражение ¬ДЕЛ(x, А) → (ДЕЛ(x, 28) → ¬ДЕЛ(x, 49)) истинно (т.е. принимает значение 1) при любом натуральном значении переменной х?
Функция ДЕЛ(n, m) истинна, когда остаток от деления n на m равен нулю: n % m == 0. Её отрицание записывается как n % m != 0.
И на этом все сложности закончились. Осталось просто переписать выражение из условия в виде функции:
def f(x, A):
return (x % A != 0) <= ((x % 28 == 0) <= (x % 49 != 0))После этого перебираем A. Формула зависит только от остатков по модулям A, 28 и 49. Поэтому для каждого A достаточно проверить один полный период длиной НОК(A, 28, 49) (НОК- наименьшее общее кратное).
Остатки повторяются периодически. Например, делимость на 28 повторяет своё значение через каждые 28 чисел, а делимость на 49 — через каждые 49.
Общий рисунок повторится после наименьшего общего кратного всех модулей. Поэтому проверка одного полного периода — не догадка и не «достаточно большой диапазон», а математически полная проверка.
from math import lcm
def f(x, A):
return (x % A != 0) <= ((x % 28 == 0) <= (x % 49 != 0))
for A in range(999, 0, -1):
period = lcm(A, 28, 49)
if all(f(x, A) for x in range(1, period + 1)):
print(A)
breakПеребор A идёт от больших значений к меньшим, поэтому первое найденное A будет наибольшим. Если ответ оказался бы у верхней границы, её следовало бы увеличить.
Теперь осталось лишь запустить нашу программу и получить ответ на это задание — число 196.
Рассмотрим задание с другой функцией:
Обозначим через ТРЕУГ(n, m, k) утверждение «существует невырожденный треугольник с длинами сторон n, m, k».
Для какого наибольшего натурального числа А логическое выражение ¬((ТРЕУГ(x, 12, 20) ≡ (¬(МАКС(x, 5) > 23))) ∧ ТРЕУГ(x, А, 3)) истинно (т.е. принимает значение 1) при любом натуральном значении переменной x?
Примечание. МАКС(a, b) = a, если a > b и МАКС(a, b) = b, если a ≤ b.
Тут нам даны сразу две функции: ТРЕУГ и МАКС. С работой второй все понятно, давайте обратим внимание на первую. Функция ТРЕУГ отсылает нас к неравенству треугольника: «сумма длин любых двух сторон строго больше длины третьей стороны».
Сначала читаем формулу словами. Внешнее отрицание относится ко всей конъюнкции внутри скобок. Значит, достаточно ошибки в любой части этой конъюнкции, чтобы вся формула стала истинной.
Функция МАКС(x, 5) выбирает большее из двух чисел. Пока x ≤ 5, результат равен 5. При x > 5 результатом становится сам x. Python выполняет это ветвление внутри max.
Если обозначить стороны треугольника как n, m и k, то требуется одновременное выполнение всех трёх неравенств:
Иными словами, на языке алгебры логики можно записать такое выражение:
n + m > k ∧ m + k > n ∧ n + k > m
А чтобы реализовать функцию ТРЕУГ в Python достаточно будет переписать это выражение, используя оператор and:
def treug(n, m, k):
return n + m > k and m + k > n and n + k > mСтрогость знака здесь принципиальна. Если сумма двух сторон равна третьей, фигура «складывается» в прямую и невырожденного треугольника не получается.
Например, стороны 3, 4 и 5 подходят: 3 + 4 > 5. А стороны 3, 4 и 7 не подходят, потому что 3 + 4 = 7, а требуется строго больше.
Ну а в качестве функции МАКС будем пользоваться встроенной в Python max. Теперь мы готовы написать функцию по формуле из условия:
def f(x, A):
return not (
(treug(x, 12, 20) == (not (max(x, 5) > 28)))
and treug(x, A, 3)
)Осталось лишь дополнить наш код циклом с перебором значений для A и x:
В этом примере все изменения истинности происходят около чисел, встречающихся в сравнениях и неравенствах треугольника. Диапазон до 200 перекрывает их с запасом.
Если вы берёте диапазон с запасом, после получения ответа полезно увеличить верхнюю границу и убедиться, что результат не изменился. Для задач только с делимостью лучше использовать точный период через НОК.
def treug(n, m, k):
return n + m > k and m + k > n and n + k > m
def f(x, A):
return not (
(treug(x, 12, 20) == (not (max(x, 5) > 28)))
and treug(x, A, 3)
)
for A in range(99, 0, -1):
if all(f(x, A) for x in range(1, 200)):
print(A)
breakЗапускаем его и видим на экране число 6. Оно и будет ответом на данное задание.
Во втором типе задания 15 появились именованные предикаты, но сама логика решения не изменилась. Мы переводим каждое определение в простое условие, записываем формулу и проверяем её при всех допустимых x.
Шаблон решения
def delit(n, m):
return n % m == 0
def treug(a, b, c):
return a + b > c and a + c > b and b + c > a
def formula(x, A):
return *1
for A in *2:
if all(formula(x, A) for x in *3):
print(A)
breakЗдесь *1 — формула из условия, *2 — диапазон и направление перебора A, *3 — достаточный диапазон x. Функции ДЕЛ, ТРЕУГ и МАКС переводите буквально.
Всегда обращайте внимание на порядок аргументов в ДЕЛ и на строгие знаки в ТРЕУГ. Помните, что одна пропущенная проверка стороны создаёт «треугольник», которого не существует. Для делимости обосновывайте диапазон через НОК, а для других функций проверяйте, что запас действительно покрывает все границы. В следующей статье разберём поразрядную конъюнкцию.
Самая частая ошибка этого типа — начать перебирать A, не разобравшись с определением новой функции. Сначала проверьте её отдельно на одном подходящем и одном неподходящем наборе аргументов. Так вы заметите перевёрнутую делимость или потерянное неравенство до запуска большой программы.
Вторая типичная ошибка связана с диапазоном x. Для делимости используйте полный период через НОК, а в задачах с неравенствами найдите все точки, около которых меняется истинность. Если диапазон взят с запасом, увеличьте его и убедитесь, что ответ не изменился.
В следующей статье сохраним тот же общий каркас перебора, но научимся читать числа как наборы двоичных разрядов и работать с поразрядной конъюнкцией.
