💾 Побитовые операции — это особый способ работы с двоичными числами
В Python выделяют 5 основных типов побитовых операций:
📍Среди всех побитовых операций особое место занимает поразрядная (побитовая) конъюнкция. Данная операция сравнивает каждый бит числа и возвращает либо 1 (True) либо 0 (False).
В этой статье разберём принцип работы данной операции в Python и покажем, как решается одно из популярных заданий ЕГЭ ⤵
→ → [START] ⤵ ⤵
Что такое поразрядная конъюнкция?
Побитовая (поразрядная) конъюнкция (побитовое 'AND') — это операция, которая сравнивает каждую пару битов двух чисел и возвращает новое число.
Другими словами:
- Исходные числа переводятся в 2 СС (*систему счисления).
- Происходит побитовое сравнение каждого числа. По каждому отдельному биту.
- Если оба исходных бита = 1, то и результат будет = 1. Во всех остальных случаях будет 0 (1 и 0, 0 и 1, 0 и 0).
- В результате получается новое число.
Принцип работы побитовой конъюнкции на примере чисел 27 и 15 ⤵
🔰Важная деталь:
При побитовой конъюнкции числа должны быть одинаковой длины
Если одно из чисел имеет меньшую длину, к его началу следует добавить нули, чтобы длины обоих чисел совпадали. Такие нули называются ведущими.
27 = 11011 # в двоичном виде
15 = 1111 → 01111
- Конъюнкция — это логическая операция, которая означает 'И'
Побитовая конъюнкция в Python
Оператор & — это и есть побитовая конъюнкция в Python.
- Как выполнить побитовую конъюнкцию в Python?
Для выполнения поразрядной конъюнкции в Python необходимо взять два числа (тип int) и поставить между ними знак (&). Python автоматически преобразует их в двоичный формат и выполнит побитовую конъюнкцию →
В качестве примера можно взять два числа из условия задачи (14 и 5) ⤵
- print() — служебная команда, используется для вывода текстовой информации на экран.
- bin() — встроенная функция в Python для перевода чисел из 10 CC в 2 CC.
🔰Важные детали:
- Побитовую конъюнкцию можно применять сразу к любому числу целых значений — двум, трём, четырём и более (23 & 15 & 14; 1 & 2 & 3 & 7 и так далее)
- Результат побитовой конъюнкции в Python — всегда целое число (int) ⤵
Знакомство с поразрядной конъюнкцией прошло успешно 😉
→ Следующий этап — разбор реального задания из ЕГЭ по информатике ⤵
Условие задачи →
Необходимо внимательно прочитать условие задачи несколько раз
[РЕШЕНИЕ] ⤵
Как записать А?
По условию задачи (А) — неотрицательное целое число.
- Как записать данное число в Python? И какие значения может принимать переменная (А)?
— Под переменной (A) в условии задачи понимается не конкретное число, а набор возможных значений. Переменная (А) может быть равна 1, 2, 15, 27, 155 и любому другому неотрицательному целому числу →
→ Чтобы перебрать разные значения переменной (A), можно воспользоваться циклом (for). Python сам будет поочерёдно присваивать переменной (А) значения из заданного набора. Это позволит проверить все возможные варианты и найти подходящий.
- Как создать цикл for в Python?
Для написания алгоритма вы можете использовать любую удобную среду (IDLE, PyCharm или Visual Studio). Для начинающих программистов рекомендую использовать именно IDLE.
В качестве примера можно взять небольшой диапазон значений в range →
- Range — это встроенная функция в Python, которая генерирует последовательность чисел
🔰Важные детали:
- Функция range() хранит в себе список чисел, который начинается с первого указанного в скобках числа и заканчивается числом, на единицу меньшим второго. Поэтому range(1,4) — это 1, 2, 3
- Цикл for + range позволяют получить все необходимые варианты для переменной (А) и выбрать подходящий
→ Запишем первую строчку кода в итоговое решение ⤵
💢 Основная программа:
⚠ Чтобы продолжить решение задачи, потребуется ввести новую переменную — flag. Назначение этой переменной и принцип её работы будут разобраны в следующей главе. →
🚩 Переменная flag в Python
flag — имя переменной, которая имеет логический тип данных (bool)
p.s. название (имя) переменной можно выбрать любое (например: a, f, qwer, count и так далее). flag - для удобства и лучшего понимания алгоритма
Зачем нужен flag?
Флаг используется как 'сигнал' или 'индикатор'. Он может сообщать программе:
- Нужно ли продолжать выполнение какого-то действия?
- Случилось ли уже определённое событие?
- Разрешён ли следующий шаг в алгоритме?
- Выполнено ли условие?
Пример ①
⇥ Переменная (flag) в данной программе ⇪ обеспечивает вывод всех значений переменной (A). Поскольку (flag) остаётся истинным (флаг - поднят), команда (print) срабатывает на каждой итерации (каждый проход цикла).
Пример ②
⇥ В этой программе ⇪ переменная (flag) управляет выводом значений переменной (A). Пока (flag) равно = False, второе условие (if) не выполняется. Как только (A) станет равна = 5, сработает первое условие: (flag) получит значение = True, и начнётся вывод значений (A) на экран.
Пример ③
⇥ Переменная (flag) в данной программе ⇪ вновь ограничит вывод определенных значений переменной (A). Поскольку (flag) изменится с истинного значения на ложное, команда (print) перестанет срабатывать после 4 итерации (когда А станет равным 5).
2 основных состояния ↑↓
Переменная (flag) может находиться в двух основных состояниях
- flag = True — флаг находится в поднятом состоянии (условие выполняется)
- flag = False — флаг опущен, условие не выполняется
flag для управления циклом FOR
используется для создания определенных условий выхода из цикла
Переменная (flag) позволяет вручную управлять досрочным выходом из циклов (for) внешних или внутренних.
Рассмотрим пример, в котором с помощью переменной (flag) осуществляется досрочный выход из цикла (for) ⤵
⇥ В данной программе переменная (flag) используется для контроля досрочного завершения цикла (for). Когда (A) достигает значения 20, выполняется первое условие: (flag) изменяется на False. Сразу после этого срабатывает второе условие, внутри которого оператор (break) прекращает выполнение цикла.
🚥 Переменная (flag) играет роль индикатора. Данный индикатор уведомляет в нужный момент о выполнении определенного условия в программе. После чего происходит остановка цикла (for).
⚠ Про break
Оператор break используется для немедленного выхода из цикла. Это может быть полезно, когда вы хотите остановить выполнение цикла при выполнении определенного условия.
🔸 Если в процессе написания алгоритма вы понимаете, что последующие вложенные циклы нецелесообразны, просто установите флаг (flag = False), чтобы затем выйти из всех уровней циклов.
🔰Важная деталь:
- Зачем нужен flag в этой программе?
— Использование данной переменной необходимо для фильтрации лишних значений. Это упрощает работу программы и значительно ускоряет её выполнение.
→ Теперь необходимо добавить (flag) в итоговое решение ⤵
💢 Основная программа:
Две неизвестные переменные в одной программе
По условию задачи и (А) и (х) — целые неотрицательные числа
- Как объявить сразу 2 неизвестные переменные в Python? И какие значения будет принимать переменная (х)?
— Под переменной (х), как и в случае с (А), в условии задачи понимается не конкретное число, а набор возможных значений →
→ Чтобы перебрать различные значения переменной (х), необходимо использовать цикл (for)
В этой программе ⇪ циклы (for) выполняются отдельно друг от друга. Переменные (A) и (x) изменяются независимо друг от друга и не имеют между собой связи.
- В чём заключается важность этого момента и как он влияет на решение задачи?
Для ответа на вопрос необходимо внимательно посмотреть на условие задачи:
Для какого наименьшего неотрицательного целого числа А формула ... тождественно истинна (при любом неотрицательном целом значении переменной x)?
- Что это значит?
— Для любого неотрицательного значения (х) переменная (А) должна подходить по формулу
Алгоритм устроен так: выбираем некоторое значение (A) и проверяем его на всех вариантах переменной (x). Если для всех (x) условие верно (формула истинна), то найденное значение (A) и является решением задачи.
- Как это сделать в Python?
— Использовать вложенный цикл (for)
Двойные циклы в Python
это структура, которая позволяет выполнять один цикл внутри другого
Пример двойного цикла ⤵
- for А in range(1, 3): — внешний цикл
- for x in range(9, 11): — внутренний (вложенный) цикл
Как работает двойной цикл:
- Запуск внешнего цикла → А = 1
- Запуск вложенного цикла для переменной (х)
- Внутренний цикл проходит все свои значения (х = 9, х = 10)
- Когда внутренний цикл закончился, внешний цикл делает шаг → А = 2
- Снова запускается внутренний цикл.
- И так пока внешний цикл не закончится.
🔰Важная деталь:
✖ Двойные циклы увеличивают время работы программы! Например, если внешний цикл повторяется 1000 раз, а внутренний 1000 раз, то получится 1 000 000 итераций!
Пример из реальной жизни:
Представим ряд столов, а за каждым столом — несколько стульев. Задача состоит в том, чтобы как можно быстрее подсчитать, общее количество стульев ⤵
Чтобы решить задачу вручную, потребуется пройтись по каждому столу и подсчитать количество стульев. Но если столов окажется 100 или 1000, такой обход займёт слишком много времени 😔
→ Подсчет количества стульев с помощью двойного цикла:
🔰Важные детали:
- Внутренний цикл повторяется полностью для каждого значения внешнего цикла.
- Двойные циклы могут использоваться для таблиц, матриц, комбинаций и поиска различных решений.
→ Теперь необходимо добавить вложенный цикл (for) для переменной (х) в итоговое решение ⤵
💢 Основная программа:
Как записать логическую формулу в Python?
— по условию задачи, логическая формула должна быть тождественно истина для всех неотрицательных (х)
Для правильной записи формулы необходимо каждый логический оператор перевести на язык Python ⤵
- not(A) or B — что означает: "НЕ А ИЛИ В"
- дизъюнкция — логическое сложение (ИЛИ)
- конъюнкция — логическое умножение (И)
→ Следующий шаг — подробный анализ нескольких основных логических операторов ⤵
Что такое импликация?
импликация — это логическая операция для описания зависимости между высказываниями
Читается: «если A, то B» или «А следует В»
- A — это условие (посылка)
- B — это вывод (следствие)
ИМПЛИКАЦИЯ ПРОВЕРЯЕТ:
→ Если первое утверждение (A) выполняется, то должно выполняться и второе утверждение (B)
ПРИМЕР ИЗ ЖИЗНИ:
Если ты пришёл в школу (A), то ты учишься (B)
А — это условие (если пришёл в школу) | B — это вывод (то будешь учиться)
- Не пришёл и не учишься → всё логично! ✅ (0 ⇒ 0)
- Не пришёл, но учишься → если занятия дистанционные ✅ (0 ⇒ 1)
- Пришёл, но не учишься → такого не может быть ❌ (1 ⇒ 0)
- Пришёл и учишься → всё отлично ✅ (1 ⇒ 1)
ТАБЛИЦА ИСТИННОСТИ:
Таблица истинности — это способ проверить, как работает логическая формула при разных значениях её переменных.
ИСПОЛЬЗОВАНИЕ В PYTHON:
Импликация работает по принципу: «если …, то …». Нарушается она только тогда, когда обещали одно (A истинно), а выполнилось другое (B оказалось ложным).
- Импликация — основа логики, математики и программирования
Что такое конъюнкция?
Конъюнкция — это логическое умножение
Читается: «A И B» или «А AND В» или «А умножить на В»
Конъюнкция истинна только тогда, когда все утверждения истинны
ИСПОЛЬЗОВАНИЕ В PYTHON:
Для проверки истинности сразу нескольких логических выражений ⤵
→ Теперь необходимо переписать основную формулу из условия задачи на язык Python ⤵
f — переменная для записи (хранения) формулы
💢 Основная программа:
🔰Важная деталь:
При создании функции (f) необходимо правильно расставить скобки: каждое выражение должно быть записано в соответствующих скобках.
Pruning метод
— метод "отбраковки" или "отсева"
Метод отсева — это стратегия (приём). Данный метод предполагает проверку и исключение заведомо «плохих» решений. Благодаря этому алгоритм работает только с подходящими вариантами.
→ Таким образом программа не тратит ресурсы и время на рассмотрение неподходящих вариантов.
⚠ Ключ pruning метода — переменная (flag)
Если значение функции оказывается ложным (f = 0), то (flag) принимает значение False (опускается) →
→ Далее срабатывает команда (break) и присходит выход из внутреннего цикла (for) ⤵
Вместо проверки всех подряд вариантов, «обрезаются» ненужные ветви →
✔ Экономия времени и ресурсов программы
3 этапа метода Puring
чтобы алгоритм сработал, будем считать функцию (f) равной 0 (f = 0)
▪Pruning метод — 1 этап
Проверка логической функции (f) на истинность при текущих значениях переменных (А) и (х).
✖ если функция (f) истинна (True), то переход к новому значению (х) — не выполняется, так как (f = 0)
✔ если функция Ложна (False) — переход ко второму этапу ⤵
▪Pruning метод — 2 этап
При текущем значении переменной (x) функция (f) обращается в ноль, следовательно, значение (A) не подходит, и флаг устанавливается в False (опускается) ⤵
🔰Важная деталь:
Переменная (flag) принимает значение (False), чтобы алгоритм не использовал текущее значение (A) как решение.
▪Pruning метод — 3 этап
Выполняется команда (break) →
Происходит выход из внутреннего цикла (for) →
✔ Переход к новому значению переменной (А)
→ После выхода из внутреннего цикла (for) программа продолжит поиск правильного решения для переменной (А)
❓В чём конкретно проявляется метод pruning
ответ: в трёх строках алгоритма
Без использования оператора (break) программа проверяла бы все 1000 значений (x) для каждого (А). Даже если уже на первом шаге ясно, что текущее (A) не подходит.
Но, благодаря данному моменту:
if f == 0:
flag = False
break
✔ Дальнейшие проверки прекращаются, а ветвь решения с данным значением (A) сразу отбрасывается →
Это и есть раннее отсечение неподходящих вариантов → типичный пример метода pruning.
→ Теперь необходимо добавить puring метод в основную программу ⤵
💢 Основная программа:
Поиск верного значения для А
Как определить подходящее для ответа значение?
С помощью условия (if) можно написать код, который сам бы отсеивал не нужные варианты.
- Что значит if в Python?
— Это оператор, позволяющий выполнить определённый участок кода только при соблюдении условий.
✔ Если условие истинно (True), то программа выполнит код, находящийся внутри блока if.
✖ Если условие не выполняется (False), код внутри блока if будет пропущен
📍Остается добавить проверку на условие в основной алгоритм и решение готово →
🔥Итоговая программа
Решение Задание №15 ЕГЭ "Побитовая конъюнкция" ⤵
Ответ: 12
👏 Поздравляю! Получен верный ответ и программа работает без ошибок
🔜Ещё материалы по теме Python: