Тип 3
В прошлой статье мы разобрали второй тип 15 заданий ЕГЭ по информатике, где научились работать с необычными функциями вроде ДЕЛ() и ТРЕУГ(), имитируя их работу на бумаге и воссоздавая в коде.
Сегодня переходим к третьему типу этих заданий, который принесёт нам новый интересный инструмент — поразрядную конъюнкцию. Эта операция может показаться сложной на первый взгляд, но на деле работает по простым и известным нам правилам.
Сначала мы детально разберём, что такое поразрядная конъюнкция и как она работает. Научимся выполнять её вручную, переводя числа в двоичную систему и применяя логическую операцию к каждому разряду. Затем посмотрим, как реализовать эту операцию в Python — к счастью, там всё гораздо проще благодаря встроенным инструментам языка.
После теоретической части перейдём к практике: решим одно задание вручную, чтобы закрепить понимание алгоритма решения, а затем разберём два примера программным методом, используя уже знакомый нам универсальный код.
Поразрядная конъюнкция
Поразрядная конъюнкция (или побитовая конъюнкция) — это операция, которая применяется к двоичным представлениям чисел. Давайте разберёмся, как она работает.
Суть операции в следующем: мы берём два числа, переводим их в двоичную систему счисления, а затем применяем логическую операцию конъюнкции (И, ∧) к каждой паре соответствующих разрядов.
Вспомним таблицу истинности конъюнкции:
То есть результат равен истине только тогда, когда оба операнда истинны (равны единице). Во всех остальных случаях результат — ложь.
Давайте найдём результат поразрядной конъюнкции для чисел 13 и 10.
Шаг 1. Переводим оба числа в двоичную систему:
- 13₁₀ = 1101₂
- 10₁₀ = 1010₂
Шаг 2. Выравниваем числа по разрядам (добавляем нули слева при необходимости):
Шаг 3. Применяем конъюнкцию к каждой паре разрядов. Разберём подробнее:
- 1-й разряд (справа): 1 И 0 = 0
- 2-й разряд: 0 И 1 = 0
- 3-й разряд: 1 И 0 = 0
- 4-й разряд: 1 И 1 = 1
Шаг 4. Переводим результат обратно в десятичную систему:
- 1000₂ = 8₁₀
Итак, поразрядная конъюнкция чисел 13 и 10 равна 8.
Теперь разберём, как её применять в языке Python. В Python поразрядная конъюнкция реализована встроенным оператором & (амперсанд). Использовать его очень просто:
Python автоматически выполняет все необходимые преобразования, так что нам не нужно вручную переводить числа в двоичную систему и обратно.
Оператор & можно использовать в любых выражениях, где требуется поразрядная конъюнкция:
Главное — не путайте оператор & с уже привычным логическим оператором and! Оператор and используется для логических выражений (True/False), а & — для поразрядных операций над числами.
Теперь, когда мы разобрались с поразрядной конъюнкцией, можем переходить к решению задач.
Алгоритм решения
Как уже было сказано ранее, первое задание мы решим исключительно вручную. Формулировка у него будет такой:
«Для какого наибольшего целого положительного числа А выражение (x & А = 0) ∨ ¬(x & 37 = 0) ∨ ¬(x & 12 = 0) истинно (т.е. принимает значение 1) при любом целом значении переменной х?»
Здесь мы имеем только дизъюнкцию. И, по выведенному ранее алгоритму решения, мы сначала ищем граничные условия для x и y, при которых значение выражение будет ложным.
Результат дизъюнкции будет ложным тогда и только тогда, когда все операнды будут ложны одновременно. Записываем по очереди:
- x & А = 0 — ложно. Значит, x & A ≠ 0
- ¬(x & 37 = 0) — ложно. Отрицание ложно, когда само выражение истинно: x & 37 = 0
- ¬(x & 12 = 0) — ложно. По аналогии с прошлым выражением: x & 12 = 0
Теперь получим систему уравнений. Все логическое выражение будет ложным, если существует такое значение x, для которого:
- x & A ≠ 0
- x & 37 = 0
- x & 12 = 0
Наша задача свелась к обычному анализу битов. Для этого запишем числа 37 и 12 в двоичном виде: 37 = 32 + 4 + 1→ 100101; 12 = 8 + 4 → 001100.
Рассмотрим выражение x & 37 = 0. Оно означает, что во всех разрядах, где у 37 стоит единица, у x обязан стоять ноль: то есть на позициях 0, 2 и 5 битов.
Аналогично поступаем и со вторым выражением. В случае с числом 12, у x должны стоять нули на месте 3 и 2 бита.
Теперь объединяем эти два условия: x не может иметь единицы в битах 0, 2, 3 и 5 (будем называть эти биты «запрещёнными»). Во всех остальных разрядах — может.
Что же до выражения x & A ≠ 0, то оно означает, что существует хотя бы один разряд, в котором у x и у A стоит единица. Но мы уже знаем, в каких битах x может быть равен 1: 1, 4, 6 и т.д. То есть во всех, кроме запрещённых.
Делаем вывод — значение x, при котором значение выражения будет ложным, существует, если:
- в A есть хотя бы один бит, который не запрещён
- x может поставить туда 1
- тогда x & A ≠ 0 выполнится (станет истинным)
- а остальные два условия уже и так будут выполненными
Значит, нужно чтобы у числа А были единицы только в запрещённых разрядах: 0, 2, 3 и 5. А чтобы такое число было наибольшим, как того требует условие задания, ставим единицы во все эти биты. Тогда число A в двоичной системе счисления будет выглядеть так: 101101. В десятичной же системе эта запись представляет собой число 45 (2^5 + 2^3 + 2^2 + 2^0).
Следовательно, наибольшее целое положительное число A, при котором логическое выражение тождественно истинно — это 45. Его и пишем в ответ.
Давайте резюмируем наши действия в виде шаблона:
- Анализируем логическое выражение. Определяем приоритет операций, переписываем выражение в однозначном виде.
- Выписываем условия ложности выражения. Здесь зачастую не обойтись без законов алгебры логики. Приводим логические выражения к системе уравнений.
- Ищем возможные значения x (граничные значения). Для этого переводим числа в двоичную систему счисления и реализуем побитовую конъюнкцию с неизвестным x, чтобы определить запрещённые биты.
- Связываем запрещённые биты с числом A. Находим, в каких битах у A должны стоять нужные значения (0 или 1). После чего собираем число из битов по степеням двойки.
И, как уже говорилось в самой первой статье, не забывайте подставлять вычисленные значения в исходное логическое выражение для проверки!
Программное решение
Итак, с ручным решением разобрались. Как вы видели, сам алгоритм у нас стандартный, меняется лишь способ нахождения значений переменной x. Но куда меньше изменений будет в программном коде.
Мы уже поняли, что в Python прекрасно реализована операция поразрядной конъюнкции через оператор &. Следовательно, достаточно лишь переписать выражение, заменив операторы алгебры логики на те, которые используются в Python.
Но самое главное — не забывайте про приоритет операторов! Покажем это на примере следующего задания:
«Для какого наименьшего неотрицательного целого числа А выражение x & 39 = 0 ∨ (x & 11 = 0 → ¬(x & А = 0)) истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?»
Попробуем переписать выражение точь-в-точь как в условии:
Обратите внимание на нашу запись импликации: x & 11 == 0 <= not (x & A == 0). Такое работать не будет! Дело в том, что Python воспринимает это как цепочку сравнений, а не как импликацию: (x & 11 == 0) and (0 <= not (x & A == 0)).
То есть сначала сравнивается x & 11 с нулём, а потом проверяется, что результат not (x & A == 0) не меньше нуля. И оба эти выражения должны быть истинны. А в выражении из условия требуется совершенно иное.
Здесь на помощь придут скобки. Нужно каждый операнд импликации обернуть в свои скобки: (x & 11 == 0) <= (not (x & A == 0)). В таком случае сначала вычисляется значение выражения x & 11 == 0, а затем — not (x & A == 0). И только потом в дело вступает «имитация» импликации в виде оператора «<=».
Перепишем функцию с учётом этих правок:
Ну а с циклом для перебора значений для A и для x вы уже знакомы:
Осталось лишь запустить программу и довольствоваться ответом — числом 36.
Пример 1
Для закрепления рассмотрим такое задание:
«Для какого наименьшего неотрицательного целого числа А выражение ((x & 52 ≠ 0) ∧ (x & 48 = 0)) → ¬(x & А = 0) истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?»
Переписываем логическое выражение из условия и не забываем про скобки у операндов импликации:
И добавляем цикл с перебором значений A и x:
Запускаем программу и видим на экране цифру 4. Это и будет ответом на данное задание.
Итак, с первыми тремя типами 15 заданий покончено. В следующей статье мы посвятим себя разбору алгоритма решения задания «с отрезками» — тех, что мы отнесли к четвёртому типу.