Как сделать поразрядную конъюнкцию в питоне

Добавил пользователь Владимир З.
Обновлено: 04.10.2024

Мы уже умеем писать функции, которые проверяют одиночные условия. Теперь научимся строить составные условия.

Хороший пример: проверка пароля. Предположим, что некий сайт при регистрации требует, чтобы пароль был длиннее восьми символов и короче двадцати символов. Да, ограничение выглядит странно, но бывает и такое.

Пароль длиннее 8 символов И пароль короче 20 символов.

Вот функция, которая принимает пароль и говорит, соответствует ли он условиям ( True ) или не соответствует ( False ):

Приоритет этого оператора ниже, чем приоритет операторов сравнения, поэтому выражение length > 8 and length отрабатывает правильно без скобок.

Операторы можно комбинировать в любом количестве и любой последовательности, но когда одновременно встречаются and и or , то приоритет лучше задавать скобками. Ниже пример расширенной функции определения корректности пароля:

Другой пример. Мы хотим купить квартиру, которая удовлетворяет условиям: площадь от 100 кв. метров и больше на любой улице ИЛИ площадь от 80 кв. метров и больше, но на центральной улице Main Street .

Напишем функцию, проверяющую квартиру. Она принимает два аргумента: площадь (число) и название улицы (строку):

И and

A	B	A and B
True	True	True
True	False	False
False	True	False
False	False	False

ИЛИ or

A	B	A or B
True	True	True
True	False	True
False	True	True
False	False	False

Задание

Джон поручил Сэму реализовать автоматическое распознавание солдат Ланнистеров на видео. Идея автоматизировать дозор крепости казалась ему привлекательной. В процессе работы Сэму понадобилось написать функцию, которая определяет, Ланнистер ли перед ним или нет. Немного подумав, Сэм выделил следующие правила определения Ланнистера:

Если у солдата доспехи красного цвета И нет щита

ИЛИ

если у солдата есть щит с изображением льва

то это Ланнистер.

Напишите функцию is_lannister_soldier() , которая принимает на вход два аргумента:

Цвет доспехов (строка). Если доспехи красные, то строка red .
None , если щита нет. Строка lion , если щит есть, и на нём изображен лев.

Функция возвращает True , если распознан Ланнистер, и False , если не распознан.

Когда будете проверять на равенство None , делайте так, как принято в настоящем коде на Python: shield is None — код будет выглядеть профессионально! Дело в том. что is работает быстрее в случае некоторых специальных значений вроде None , True и False .

Советы

Определения

Если вы столкнулись с трудностями и не знаете, что делать, задайте вопрос в нашем большом и дружном сообществе

Кортежи (tuples) очень похожи на списки, но являются неизменяемыми. Как мы видели, использование изменяемых объектов может приводить к неприятным сюрпризам.

Кортежи пишутся в круглых скобках. Если элементов $>1$ или 0, это не вызывает проблем. Но как записать кортеж с одним элементом? Конструкция (x) абсолютно легальна в любом месте любого выражения, и означает просто x . Чтобы избежать неоднозначности, кортеж с одним элементом x записывается в виде (x,) .

Скобки ставить не обязательно, если кортеж — единственная вещь в правой части присваивания.

Работать с кортежами можно так же, как со списками. Нельзя только изменять их.

В левой части присваивания можно написать несколько переменных через запятую, а в правой кортеж. Это одновременное присваивание значений нескольким переменным.

Сначала вычисляется кортеж в правой части, исходя из старых значений переменных (до этого присваивания). Потом одновременно всем переменным присваиваются новые значения из этого кортежа. Поэтому так можно обменять значения двух переменных.

Это проще, чем в других языках, где приходится использовать третью переменную.

2. Множества¶

В соответствии с математическими обозначениями, множества пишутся в фигурных скобках. Элемент может содержаться в множестве только один раз. Порядок элементов в множестве не имеет значения, поэтому питон их сортирует. Элементы множества могут быть любых типов.

Принадлежит ли элемент множеству?

Множество можно получить из списка, или строки, или любого объекта, который можно использовать в for цикле (итерабельного).

Как записать пустое множество? Только так.

Дело в том, что в фигурных скобках в питоне пишутся также словари, что мы будем их обсуждать в следующем параграфе. Когда в них есть хоть один элемент, можно отличить словарь от множества. Но пустые фигурные скобки означают пустой словарь.

Работать с множествами можно как со списками.

Это генератор множества (set comprehension).

Проверка того, является ли одно множество подмножеством другого.

Разность и симметричная разность.

Множества (как и списки) являются изменяемыми объектами. Добавление элемента в множество и исключение из него.

Как и в случае += , можно скомбинировать теоретико-множественную операцию с присваиванием.

Приведенные выше операции можно записывать и в другом стиле

Существуют также неизменяемые множества. Этот тип данных называется frozenset . Операции над такими множествами подобны обычным, только невозможно изменять их, а всего лишь добавлять и исключать элементы.

3. Словари¶

Словарь содержит пары ключ — значение, причем порядо значений несущественен. Это один из наиболее полезных и часто используемых типов данных в питоне.

Можно узнать значение, соответствующее некоторому ключу. Словари реализованы как хэш-таблицы, так что поиск даже в больших словарях очень эффективен. В языках низкого уровня (например, C) для построения хэш-таблиц требуется использовать внешние библиотеки и писать заметное количество кода. В скриптовых языках (perl, python, php) они уже встроены в язык, и использовать их очень легко.

Можно проверить, есть ли в словаре данный ключ.

Можно присваивать значения как имеющимся ключам, так и отсутствующим (они добавятся к словарю).

Длина — число ключей в словаре.

Можно удалить ключ из словаря.

Метод get , если он будет вызван с отсутствующим ключом, не приводит к ошибке, а возвращает специальный объект None . Он используется всегда, когда необходимо указать, что объект отсутствует. В какой-то мере он аналогичен null в C. Если передать методу get второй аргумент — значение по умолчанию, то будет возвращаться это значение, а не None .

Словари обычно строят последовательно: начинают с пустого словаря, а затем добавляют ключи со значениями.

А это генератор словаря (dictionary comprehension).

Ключами могут быть любые неизменяемые объекты, например, целые числа, строки, кортежи.

Словари, подобно спискам, можно использовать в for циклах. Перебираются имеющиеся в словаре ключи, причем в каком-то непредсказуемом порядке.

Метод keys возвращает список ключей, метод values — список соответствующих значений (в том же порядке), а метод items — список пар (ключ, значение). Точнее говоря, это не списки, а некоторые объекты, которые можно использовать в for циклах или превратить в списки функцией list . Если хочется написать цикл по упорядоченному списку ключей, то можно использовать sorted(d.keys)) .

Что есть истина? И что есть ложь? Подойдём к этому философскому вопросу экспериментально.

На выражения, стоящие в булевых позициях (после if , elif и while ), неявно напускается функция bool . Некоторые объекты интерпретируются как False : число 0, пустая строка, пустой список, пустое множество, пустой словарь, None и некоторые другие. Все остальные объекты интерпретируются как True . В операторах if или while очень часто используется список, словарь или что-нибудь подобное, что означает делай что-то если этот список (словарь и т.д.) не пуст.

Заметим, что число с плавающей точкой 0.0 тоже интерпретируется как False . Это использовать категорически не рекомендуется: вычисления с плавающей точкой всегда приближённые, и неизвестно, получите Вы 0.0 или 1.234E-12 . Лучше напишите if abs(x) .

4. Функции¶

Это простейшая в мире функция. Она не имеет параметров, ничего не делает и ничего не возвращает. Оператор pass означает "ничего не делай"; он используется там, где синтаксически необходим оператор, а делать ничего не нужно, например, после if или elif , после def и т.д..

Не строгое, но интуитивно понятное определение логического выражения таково: логическое выражение - это последовательность первичных логических выражений, объединенных скобками и знаками логических операций. Заметьте, что точно также можно определить понятие арифметического или строкового выражения. Разница лишь в задании первичных выражений и операций над ними.

Какие же логические операции применяются при построении логических выражений в логике, в языках программирования и, в частности, в Python?

Давайте совершим небольшой экскурс в основы логики. Логические операции - функции, определенные над логическими переменными, результат которых также имеет тип bool . Уникальной особенностью логических функций является существование базиса - конечного набора функций, позволяющего любую логическую функцию с любым числом переменных задать формулой (логическим выражением), использующим только функции базиса. Можно доказать, что таким базисом является набор из трех функций: отрицание, конъюнкция, дизъюнкция.

Отрицание (в Python существуют два варианта этой операции - not и ~ ) - это унарная операция, изменяющая значение аргумента на противоположное - True на False и обратно.

Конъюнкция, называемая также операцией И , логическим умножением, (в Python существуют два варианта этой операции - and и & ) - это бинарная операция, истинная тогда и только тогда, когда оба операнда операции истинны.

Дизъюнкция, называемая также операцией ИЛИ , логическим сложением, (в Python существуют два варианта этой операции - or и | ) - это бинарная операция, ложная тогда и только тогда, когда оба операнда операции ложны.

Эти операции имеют разный приоритет при вычислении логических выражений. Высший приоритет имеет операция отрицания, затем логическое умножение (конъюнкция), затем логическое сложение (дизъюнкция).

Из логики известно, что базис можно сократить до одной функции. Теоретически это интересно, но практически нецелесообразно из-за растущей сложности формул, задающих логическое выражение. Поэтому в языках программирования базис обычно расширяется, в него добавляется эквивалентность (в Python - это == ) и ее отрицание, операция, называемая Исключающее Или, сложение по модулю 2 (в Python - это ^ ). Таким образом базис логических функций, используемых в языке Python, состоит из 5 функций, три из которых существуют в двух вариантах.

Отметим одну важную особенность логических выражений. Числа сами по себе не являются первичными логическими выражениями, но в Python при построении логических выражений можно использовать числа в качестве первичных выражений. В этом случае арифметическое выражение, имеющее значение 0, интерпретируется как False , все остальные значения - True . Заметьте, арифметическое выражение в этом случае не обязательно имеет тип int , допустим любой арифметический тип. Таким образом понятие логического выражения в Python расширяется, - оно строится из первичных логических выражений, арифметических выражений, объединяя их скобками и знаками операций. Как следствие, операнды логических операций могут иметь как тип bool , так и арифметический тип. Это еще одна сложность, затуманивающая понимание логических операций, допустимых в Python. Особенно неприятно, когда операнды имеют разные типы. Еще одно следствие, - логическое выражение не обязательно имеет тип bool , - его значением может быть число арифметического типа.

Поговорим теперь о том, почему базисные логические операции существуют в двух вариантах. Это не является уникальной особенностью Python. Практически такая ситуация существует в большинстве языков программирования. Объясняется это тем, что в программировании логические выражения имеют не два, а три значения - истина, ложь, неопределенность. Неопределенность не есть признак ошибки, а признак некоторой распознаваемой ситуации. Поэтому вместо классической конъюнкции и дизъюнкции полезно иметь их варианты - условные операции, учитывающие возможность неопределенности операнда, не приводящие к возникновению ошибки в работе программы.

Есть еще одна причина, по которой полезно иметь логические операции в двух вариантах, один из которых предполагает выполнение логических операций над булевскими операндами, что соответствует классической логике, другой - предполагает выполнение операций над целыми числами, когда целое число рассматривается как строка битов, представляющих число в двоичной системе счисления. Тогда операция выполняется над соответствующими парами бит операндов, формируя новое число. Такая возможность позволяет эффективно решать целый ряд задач, возникающих в программировании. Обычная практика, когда операция применяется либо к целым числам, либо к булевским выражениям. В языке Python эти два способа работы смешиваются, что будет показано на примерах.

Задание 15 № 9804

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 32 do begin

for x := 0 to 32 do

if not (((x and 29) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

if B then begin

Приведем аналогичную программу на языке Python (Владимир Юрьевич Ламок).

for a in range (1, 65):

for x in range (0, 65):

if ((x & 29 != 0) Ответ: 12

Задание 15 № 34506

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Имеем импликацию Z₁₇Z_A → Z₂₅ или Z_{(17 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀ = 11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 17₁₀ = 10001₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂ = 8₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

for x := 0 to 31 do

if not (((x and 25) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

if B then begin

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 17 хватит пяти разрядов. Программа выведет ответ 8.

Задание 15 № 34508

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Имеем импликацию Z₁₂Z_A → Z₂₉ или Z_{(12 or A)} → Z₂₉. Запишем число 29 в двоичной системе счисления: 29₁₀ = 11101₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12₁₀ = 01100₂, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10001₂ = 17₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 31 do begin

for x := 0 to 31 do

if not (((x and 29) = 0) or ((x and 12) <> 0) or ((x and A) <> 0)) then

if B then begin

Приведём решение на языке Python.

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 29 и 12 хватит пяти разрядов. Программа выведет ответ 17.

Задание 15 № 34509

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?

Преобразуем выражение по законам алгебры логики:

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Имеем импликацию Z₁₇Z_A → Z₂₈Z₄₅ или Z_{(17 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀ = 11100₂, 45₁₀ = 101101₂, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z_{(17 or А)} = Z₆₁.

Импликация принимает вид Z_{(17 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 17 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Тем самым, искомым числом является А = 101100₂ = 44₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

for A := 0 to 63 do begin

for x := 0 to 63 do

if not (((x and 28) = 0) and ((x and 45) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

if B then begin

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 17 хватит шести разрядов. Программа выведет ответ 44.

Читайте также: