Главная / ЕГЭ Информатика / Задание №15 / ID 32518
ID 32518 ЕГЭ Информатика Линия №15 СдамГИА ID: 10392 Анализ информационных моделей
✈️ TG ВК Следующая ⏭️
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14&5  =  11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула

$( ( x\28 не = 0 ) \vee ( x\45 не = 0 ) ) arrow ( ( x\17=0 ) arrow ( x\A не = 0 ) )$

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?
💡 Пошаговый разбор и решение:
Преобразуем выражение по законам алгебры логики:

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

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.
Имеем импликацию Z17ZA → Z28Z45 или Z(17 or А) → Z(28 or 45). Поскольку 2810  =  111002, 4510  =  1011012, для побитовой дизъюнкции имеем: 28or45  =  111101. Тогда Z(17 or А) = Z61.
Импликация принимает вид Z(17 or A) → Z61. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

17: 010001
 A:  1?110?
61: 111101

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

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

var
A, x: integer;
B: boolean;
begin
for A := 0 to 63 do begin
B := True;
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
B := False;
if B then begin
writeln(A);
break;
end;
end;
end.

Приведем аналогичную программу на языке Python.

for A in range(64):
B = True
for x in range(64):
if ((x&28==0) and (x&45==0) or (x&17!=0) or (x&A!=0))==0:
B=False
if B:
print(A)
break

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

Ответ: 44.
Правильный ответ: 44
📚 Похожие разобранные задания по предмету:
ID 33977 • Задание №24
Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите максимальное количество...
Смотреть разбор ↗
ID 33913 • Задание №23
Сколько существует различных наборов значений логических переменных x1, x2, ...x8, y1, y2, ...y8, которые удов...
Смотреть разбор ↗
🔗 Другие задания линии №15 по предмету Информатика:
ID 32409 Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, ... ID 32410 Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14... ID 32411 Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14&5  =... ID 32412 Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12... ID 32413 Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14...
← Предыдущее задание 📚 Все задания по предмету Следующее задание →