Тип 2
В прошлой статье мы познакомились с типизацией 15 заданий ЕГЭ по информатики и освоили алгоритм ручного решения первого типа этих заданий. А также вывели универсальный код для решения всех первых трёх типов 15 заданий.
Теперь настало время двигаться дальше и разобрать второй тип. Здесь, как уже говорилось ранее, нам предстоит поработать с некоторыми необычными функциями, работу которых мы будем либо имитировать на бумаге, либо воссоздавать в коде.
Далее рассмотрим одно ручное решение и на двух примерах вспомним программный метод и адаптируем его под новый тип.
Алгоритм решения
Сразу рассмотрим вот такую формулировку 15 задания:
«Обозначим через ДЕЛ(n, m) утверждение "натуральное число n делится без остатка на натуральное число m". Для какого наименьшего натурального числа A логическое выражение (ДЕЛ(x, 9) → ¬ ДЕЛ(x, 6)) ∨ (x + A ≥ 100) истинно (т.е. принимает значение 1) при любом целом положительном значении переменной x?»
Давайте рассуждать. В выражении мы имеем импликацию ДЕЛ(x, 9) → ¬ ДЕЛ(x, 6). И дизъюнкцию результата импликации с выражением x + A ≥ 100.
Нам нужно определить, в каких ситуациях все выражение будет ложным, а затем, на основе этих данных, подобрать значения для неизвестного числа А. Начнём с импликации.
По таблице истинности импликации такое выражение будет давать истину всегда, когда второй операнд (справа) больше или равен первому (слева). То есть слева может быть как ложь, так и истина, но справа должна быть истина во всех случаях, кроме такого, когда слева ложь:
- 0 → 1 = истина
- 1 → 1 = истина
- 0 → 0 = истина
- 1 → 0 = ложь.
Нас интересует здесь только последний случай. Иными словами, число x должно делиться на 9 без остатка (истинность ДЕЛ(x, 9)) и вместе с этим должно делиться на 6 (ложность ¬ ДЕЛ(x, 6))
Значит, нам нужно рассмотреть только те случаи, когда значение x кратно и 9, и 6 — это будет число 18 и все кратные ему (число 18 — это наименьшее общее кратное 6 и 9).
Теперь переходим ко второй части — дизъюнкции. Дизъюнкция будет ложной тогда и только тогда, когда оба операнда будут ложны одновременно. То есть, когда выражение будет возвращать ложь, в то время, когда импликация тоже ложна, все логическое выражение будет ложно.
Отсюда можно найти значение для числа A: A < 100 – x. Не забывайте, что при таких значениях A (меньших 100 – x) мы будем получать ложь!
Но вернёмся к x. Ранее мы уже определили, что он может принимать значения, кратные 18. Максимальное же значение A мы получим при минимальном значении x — то есть, когда x будет равен 18. Отсюда вычисляем A:
A < 100 – 18
⇒ A < 82.
Таким образом, мы установили, что при значениях A, меньших 82, выражение x + A ≥ 100 будет ложным, что, в свою очередь, повлечёт за собой ложность всего логического выражения (при x = 18):
- ДЕЛ(18, 9) — истина
- ¬ ДЕЛ(18, 6)) — ложь
- (ДЕЛ(18, 9) → ¬ ДЕЛ(18, 6)) — ложь
- (18 + 81 ≥ 100) — ложь
- (ДЕЛ(18, 9) → ¬ ДЕЛ(18, 6)) ∨ (18 + 81 ≥ 100) — ложь
Отсюда делаем вывод, что значение A должно быть не менее 82 (A ≥ 82), тогда второй операнд в дизъюнкции будет истинным и все выражение также истинным. Ну а наименьшим значением тут будет число 82. Его и записываем в ответ.
Программное решение
Что же, алгоритм ручного решения рассмотрели. Все действия идут строго по плану, который мы вывели еще в прошлой статье. Так что теперь перейдём к программному решению второго типа 15 заданий.
На очереди у нас такое задание:
«Обозначим через ДЕЛ(n, m) утверждение "натуральное число n делится без остатка на натуральное число m". Для какого наибольшего натурального числа А логическое выражение ¬ДЕЛ(x, А) → (ДЕЛ(x, 28) → ¬ДЕЛ(x, 49)) истинно (т.е. принимает значение 1) при любом натуральном значении переменной х?»
Для начала давайте подумаем, как записать функцию ДЕЛ(n, m). Логично предположить, что нам следует применить операцию взятия остатка от деления (оператор «%») числа n на m («n%m») и потребовать, чтобы результат этой операции был равен нулю: «n % m == 0». Следовательно, если требуется инверсия этой функции (¬ДЕЛ(x, А)), то, напротив, требуем, чтобы остаток от деления не равнялся нулю: «n % m != 0».
И на этом все сложности закончились. Осталось просто переписать выражение из условия в виде функции:
А дальше идёт уже знакомый код с перебором значений A и x:
Напомним, что здесь мы для каждого рассматриваемого значения A требуем, чтобы функция f() возвращала истину для всех значений x из диапазона от 1 до 1000. Верхние границы для A и x подбираются опытным путём.
Теперь осталось лишь запустить нашу программу и получить ответ на это задание — число 196.
Пример 1
Рассмотрим задание с другой функцией:
«Обозначим через ТРЕУГ(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.»
Тут нам даны сразу две функции: ТРЕУГ() и МАКС(). С работой второй все понятно, давайте обратим внимание на первую. Функция ТРЕУГ() отсылает нас к неравенству треугольника: «сумма длин любых двух сторон строго больше длины третьей стороны».
Если обозначить стороны треугольника как n, m и k, то требуется одновременное выполнение всех трёх неравенств:
- n + m > k
- m + k > n
- n + k > m
Иными словами, на языке алгебры логики можно записать такое выражение:
n + m > k ∧ m + k > n ∧ n + k > m
А чтобы реализовать функцию ТРЕУГ() в Python достаточно будет переписать это выражение, используя оператор and:
Ну а в качестве функции МАКС() будем пользоваться встроенной в Python max(). Теперь мы готовы написать функцию по формуле из условия:
Осталось лишь дополнить наш код циклом с перебором значений для A и x:
Запускаем его и видим на экране число 6. Оно и будет ответом на данное задание.
На этом мы завершим разбор алгоритма решения второго типа 15 заданий. В следующей статье поработаем с поразрядной конъюнкцией и научимся решать задания третьего типа.