В прошлой статье мы разобрали второй тип 15 заданий ЕГЭ по информатике, где научились работать с необычными функциями вроде ДЕЛ и ТРЕУГ, имитируя их работу на бумаге и воссоздавая в коде.
Сегодня переходим к третьему типу этих заданий, который принесёт нам новый интересный инструмент — поразрядную конъюнкцию. Эта операция может показаться сложной на первый взгляд, но на деле работает по простым и известным нам правилам.
Сначала мы детально разберём, что такое поразрядная конъюнкция и как она работает. Научимся выполнять её вручную, переводя числа в двоичную систему и применяя логическую операцию к каждому разряду. Затем посмотрим, как реализовать эту операцию в Python — к счастью, там всё гораздо проще благодаря встроенным инструментам языка.
После теоретической части перейдём к практике: решим одно задание вручную, чтобы закрепить понимание алгоритма решения, а затем разберём два примера программным методом, используя уже знакомый нам универсальный код.
Поразрядная конъюнкция (или побитовая конъюнкция) — это операция, которая применяется к двоичным представлениям чисел. Давайте разберёмся, как она работает.
Удобно представить двоичные разряды как ряд выключателей. Единица означает, что выключатель включён, ноль — выключен. Операция И оставляет свет только там, где включены оба выключателя.
Каждый разряд отвечает за свою степень двойки: справа налево это 1, 2, 4, 8, 16, 32 и так далее. Поэтому после поразрядной операции мы можем собрать десятичное число из оставшихся единичных разрядов.
Суть операции в следующем: мы берём два числа, переводим их в двоичную систему счисления, а затем применяем логическую операцию конъюнкции (И, ∧) к каждой паре соответствующих разрядов.
Вспомним таблицу истинности конъюнкции:
То есть результат равен истине только тогда, когда оба операнда истинны (равны единице). Во всех остальных случаях результат — ложь.
Давайте найдём результат поразрядной конъюнкции для чисел 13 и 10.
Шаг 1. Переводим оба числа в двоичную систему:
Шаг 2. Выравниваем числа по разрядам (добавляем нули слева при необходимости):
Шаг 3. Применяем конъюнкцию к каждой паре разрядов. Разберём подробнее:
Шаг 4. Переводим результат обратно в десятичную систему:
Итак, поразрядная конъюнкция чисел 13 и 10 равна 8.
Посмотрим на тот же результат через степени двойки. В числе 13 включены разряды 8, 4 и 1, а в числе 10 — разряды 8 и 2. Общим оказался только разряд 8, поэтому ответ равен 8.
Ещё один быстрый пример: выполним поразрядную конъюнкцию чисел 12 и 10. Число 12 — это 1100₂, число 10 — 1010₂. Общая единица стоит только в разряде 8, поэтому результат поразрядной конъюнкции — число 8.
Теперь разберём, как её применять в языке Python. В Python поразрядная конъюнкция реализована встроенным оператором & (амперсанд). Использовать его очень просто:
result = 13 & 10
print(result)
>>>8Python автоматически выполняет все необходимые преобразования, так что нам не нужно вручную переводить числа в двоичную систему и обратно.
Оператор & можно использовать в любых выражениях, где требуется поразрядная конъюнкция:
x = 42
y = 27
z = x & y
print(z)
>>>10Главное — не путайте оператор & с уже привычным логическим оператором and! Оператор and используется для логических выражений (True/False), а & — для поразрядных операций над числами.
Выражение 5 and 3 в Python работает с истинностью объектов и вернёт 3, а 5 & 3 сравнит двоичные разряды и вернёт 1. В задачах этого типа нужен именно амперсанд!
Теперь, когда мы разобрались с поразрядной конъюнкцией, можем переходить к решению задач.
Как уже было сказано ранее, первое задание мы решим исключительно вручную. Формулировка у него будет такой:
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наибольшего целого положительного числа А логическое выражение (x & А = 0) ∨ ¬(x & 37 = 0) ∨ ¬(x & 12 = 0) истинно (т.е. принимает значение 1) при любом целом значении переменной х?
В формуле есть только дизъюнкции. Поэтому сначала определим, при каких x все три её части могли бы одновременно стать ложными.
Результат дизъюнкции будет ложным тогда и только тогда, когда все операнды будут ложны одновременно. Записываем по очереди:
Теперь получим систему уравнений. Все логическое выражение будет ложным, если существует такое значение x, для которого:
Наша задача свелась к обычному анализу битов. Для этого запишем числа 37 и 12 в двоичном виде: 37 = 32 + 4 + 1→ 100101; 12 = 8 + 4 → 001100.
Пронумеруем позиции справа, начиная с нуля. Тогда бит 0 имеет вес 1, бит 1 — вес 2, бит 2 — вес 4, бит 3 — вес 8. Такая нумерация совпадает с показателем степени двойки.
Рассмотрим выражение 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 разрядах: 0, 2, 3 и 5. Для наибольшего A ставим единицы во все эти разряды: A = 101101₂ = 2⁵ + 2³ + 2² + 2⁰ = 45.
Можно заметить короткую проверку: запрещённые биты — это единицы, которые встречаются хотя бы в одном из чисел 37 и 12. Поразрядное ИЛИ этих масок даёт 37 | 12 = 45.
Запоминать оператор | для ручного решения не обязательно. Важно понимать смысл: собираем в A все позиции, где единица стоит у 37 или у 12.
Почему нельзя добавить ещё один бит? Если поставить единицу, например, в разряд 1, выберем x = 2. Тогда x & 37 = 0 и x & 12 = 0, но x & A ≠ 0. Все три части исходной дизъюнкции станут ложными.
Следовательно, наибольшее целое положительное число A, при котором логическое выражение тождественно истинно — это 45. Его и пишем в ответ.
Давайте резюмируем наши действия в виде шаблона:
И, как уже говорилось в самой первой статье, не забывайте подставлять вычисленные значения в исходное логическое выражение для проверки!
Что же, с ручным решением разобрались. Как вы видели, сам алгоритм у нас стандартный, меняется лишь способ нахождения значений переменной x. Но куда меньше изменений будет в программном коде.
Мы уже поняли, что в Python прекрасно реализована операция поразрядной конъюнкции через оператор &. Следовательно, достаточно лишь переписать выражение, заменив операторы алгебры логики на те, которые используются в Python.
Но самое главное — не забывайте про приоритет операторов! Покажем это на примере следующего задания:
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А логическое выражение x & 39 = 0 ∨ (x & 11 = 0 → ¬(x & А = 0)) истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?
Попробуем переписать выражение точь-в-точь как в условии:
def f(x, A):
# Неверная запись: Python считает <= частью цепочки сравнений
return x & 39 == 0 or (x & 11 == 0 <= not (x & A == 0))Обратите внимание на нашу запись импликации: 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). И только потом в дело вступает «имитация» импликации в виде оператора «<=».
Перепишем функцию с учётом этих правок:
def f(x, A):
return (x & 39 == 0) or (
((x & 11) == 0) <= (not ((x & A) == 0))
)Ну а с циклом для перебора значений для A и для x вы уже знакомы:
def f(x, A):
return (x & 39 == 0) or (
((x & 11) == 0) <= (not ((x & A) == 0))
)
for A in range(0, 100):
if all(f(x, A) for x in range(0, 128)):
print(A)
breakПоскольку A < 100, все используемые числа помещаются в 7 бит. Поэтому достаточно проверить x от 0 до 127. Программа выведет 36.
Числа от 0 до 127 перебирают все варианты семи младших битов: от 0000000₂ до 1111111₂. Более старшие биты не влияют на & с числами меньше 128.
Именно поэтому граница 128 здесь обоснована двоичной длиной, а не выбрана случайно. Если в условии появится число 200, понадобится уже восемь бит и диапазон до 255 включительно.
Для закрепления рассмотрим такое задание:
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А логическое выражение ((x & 52 ≠ 0) ∧ (x & 48 = 0)) → ¬(x & А = 0) истинно (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?
Переписываем логическое выражение из условия и не забываем про скобки у операндов импликации:
def f(x, A):
return ((x & 52 != 0) and (x & 48 == 0)) <= (not (x & A == 0))И добавляем цикл с перебором значений A и x:
def f(x, A):
return (
((x & 52) != 0) and ((x & 48) == 0)
) <= (not ((x & A) == 0))
for A in range(0, 100):
if all(f(x, A) for x in range(0, 128)):
print(A)
breakЗапускаем программу и видим на экране цифру 4. Это и будет ответом на данное задание.
Проверим смысл ответа. Посылка может быть истинной только тогда, когда x имеет общий бит с 52, но не имеет общих битов с 48. Числа 52 и 48 отличаются как раз битом со значением 4.
Значит, для каждого такого x обязательно включён бит 4. Чтобы заключение ¬(x & A = 0) было истинным, достаточно взять A = 4. Меньшие A нужного бита не содержат.
В третьем типе задания 15 мы рассматриваем числа как наборы включённых двоичных разрядов. Оператор & оставляет единицу только в тех позициях, где она есть у обоих чисел, а and связывает уже готовые логические условия.
Всегда обращайте внимание на скобки: запись ((x & 11) == 0) сначала вычисляет маску, а затем сравнивает её с нулём. Помните о нумерации битов с нуля и обосновывайте диапазон x количеством значимых разрядов. В следующей статье перейдём к формулам с отрезками.
Шаблон решения
def f(x, A):
return *1
for A in *2:
if all(f(x, A) for x in *3):
print(A)
breakЗдесь *1 — формула из условия, *2 — диапазон и направление перебора A (для наименьшего — range(0, N), для наибольшего — range(N, -1, -1)), *3 — диапазон x, например range(0, 2 ** k), где k — число значимых разрядов в масках. Каждую маску сравнивайте в скобках: (x & 52) != 0.
В следующей статье перейдём к четвёртому типу задания 15 — логическим формулам с отрезками.
