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

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

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

(((x&13 ⁄= 0)∨ (x&39 = 0)) → (x&13 ⁄= 0))∨((x&A = 0) ∧(x&13 = 0))

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

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

Враги хотят чтобы одновременно $x&39 = 0$ , $x&13 = 0$ , $x&A ⁄= 0$ .

$13 = 001101 10 2$

$3910 = 1001112$

Для выполнения первого условия $x$ должен иметь вид _ _ _ _ 0 0 _ 0. На месте _ может стоять 1 или 0.

Для выполнения и второго условия $x$ должен иметь вид _ _ 0 _ 0 0 0 0.

Для выполнения третьего условия единиц в $x$ должно быть как можно больше. Тогда он имеет вид …1 1 0 1 0 0 0 0.

Друзья хотят такое максимальное $A$ чтобы $x&A = 0$ . Тогда на местах с единицами в $x$ будут нули, а на местах нулей будут единицы. Значит $A = 1011112 = 47$ .

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

def f(a):
    for x in range(1, 1000):
        if ((((x & 13 != 0) or (x & 39 == 0)) <= (x & 13 != 0)) or ((x & a == 0) and (x & 13 == 0))) == 0:
            return False
    return True

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

Ответ: 47