Задача к ЕГЭ по информатике на тему «побитовая конъюнкция» №1

Просмотров 8 Комментарии 0

Введём выражение $M &K,$ обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее неотрицательное число $A$ , такое что выражение

(x&25 ⁄= 0) → ((x&17 = 0) → (x&A ⁄= 0))

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

Решение руками:

Мечты врагов:

( ||| x&25 ⁄= 0 { || x&17=0 |( x&A=0

Переведем числа в $2$ -сс. $25 = 110012$ . $17 = 100012$ . Проведем поразрядную конъюнцию с $x$ . Получаем, что $x = 01∗ ∗02$ . Запишем мечты врагов: «Вот бы $x$ давал в поразрядной конъюнкции с $A$ нолик».

Теперь играем за друзей. Друзья не хотят, чтобы $x$ в поразрядной конъюнкции с $A$ давал ноль. Т.к. у нас требуют наименьшее число $A$ , на место звездочек ставим нули. Получаем число $1000 = 8 2$ .

Решение программой:

def f(a):
    for x in range(1000):
        if ((x & 25 != 0) <= ((x & 17 == 0) <= (x & a != 0))) == 0:
            return False
    return True

for a in range(1, 1000):
    if f(a):
        print(a)
        break

Ответ: 8