Поразрядная конъюнкция. Задача №18 из ЕГЭ по информатике.
Задача №18 является заданием повышенной сложности и проверят знание основных понятий и законов математической логики. Это задание за многолетнюю историю ЕГЭ претерпевало ряд изменений. Сначала это была задача на нахождение минимальной/максимальной длины отрезка, затем мы работали с элементами множеств, далее появились битовые цепочки и делители, наконец, последнее на сегодняшний день – поразрядные конъюнкции.
Рекомендуемое время для 18-го задания – 3 минуты. Поэтому, хотя эта задача, как и все остальные, подробно разобрана на сайте http://kpolyakov. spb. ru/school/ege. htm , многие учителя информатики и все, кто связан с подготовкой к сдаче ЕГЭ, продолжают искать более простые алгоритмы решения этой задачи.
Есть решения, основанные на использовании построения таблиц истинности. Интересная статья опубликована в журнале «Потенциал» №2 2016, также посвящена разбору 18-го задания. На летней школе в МГУ для учителей информатики выступление сотрудника ф-та ВМК , было встречено слушателями аплодисментами. Предложенный им метод основан на анализе логического выражения. Посмотреть презентацию можно по ссылке http://www. vmk-edu. ru/news/343 .
В этой статье хочу показать, как мы с учениками решаем эту задачу. Сразу оговорюсь, что столь простой способ, пригоден лишь к заданиям определённого вида: когда выражение содержит не более трёх конъюнкций. Но задания такого вида встречаются достаточно часто в работах, так что, может, кому-то это окажется полезным.
Итак, во всех заданиях на поразрядную конъюнкцию ищут либо наименьшее, либо наибольшее десятичное число А, такое, что заданное выражение будет тождественно истинно при любом натуральном значении переменной Х. Рассмотрим оба вида заданий1.
1) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение
(X & 49 ? 0) > ((X & 33 = 0) > (X & A ? 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
Решение.
Сначала преобразуем выражение, избавившись от импликации по формуле A>B = A+B
Получим выражение: (X & 49 ? 0) + (X & 33 = 0) + (X & A ? 0) = 1
Это, в свою очередь, можно переписать так:
(X & 49 = 0) + (X & 33 ? 0) + (X & A ? 0) = 1
Всё выражение будет истинным, когда хотя бы одна из трёх его составляющих будет истинна.
Перейдём к двоичной записи чисел.
4910=1100012
3310=1000012
Биты 5 4 3 2 1 0
49 110001 = 0
33 100001 ? 0
А ?????? ? 0
Теперь будем побитово подбирать такое минимальное А, чтобы наше выражение было верным.
Рассмотрим младшие биты. Для 49: 1=0 – неверно; для 33: 1? 0 – верно. Поскольку X & 33 ? 0 в младшем бите даёт нам истину, то в младший бит А мы вольны поставить что угодно: хоть «0», хоть «1». Поскольку мы ищем минимальное значение, ставим «0».
49 110001 = 0
33 100001 ? 0
А ?????0 ? 0
Аналогично рассматриваем следующий бит. Для 49: 0=0 сразу даёт истину, так что соответствующий бит А опять равен «0».
49 110001 = 0
33 100001 ? 0
А ????00 ? 0
Ещё два бита дают уже рассмотренную ситуацию, получаем:
49 110001 = 0
33 100001 ? 0
А ??0000 ? 0
Рассматриваем 4-ый бит: для 49: 1=0 – неверно; для 33: 0? 0 – неверно. Значит в 4-ый бит А мы должны поставить «1», так как по условию X & A ? 0
49 110001 = 0
33 100001 ? 0
А ?10000 ? 0
Последний бит даёт истину для 33: 1? 0, поэтому 5-ый бит А равен «0»
49 110001 = 0
33 100001 ? 0
А 010000 ? 0
Итак, получили А=100002=1610
Ответ: 16
2) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение
(X & A ? 0 ) > ((X & 20 = 0) > (X & 5 ? 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
Решение.
Как и в задании на поиск минимального значения сначала преобразуем выражение. Получим:
(X & A = 0 ) + (X & 20 ? 0) + (X & 5 ? 0)=1
Перейдём к двоичной записи чисел.
2010=101002
510=001012
Биты 4 3 2 1 0
20 10100 ? 0
5 00101 ? 0
А ????? = 0
Так же как и в 1-ом задании, будем побитово рассматривать каждое выражение. Если какое-либо из них даёт истину, то в соответствующий бит А мы можем поставить что угодно, но так как мы ищем максимальное значение, то будем ставить «1». В противном случае, бит А должен быть равен «0», так как истинность всего выражения должна будет обеспечить конъюнкция X & A = 0.
0-ые биты. Для 20: 0 ? 0 – ложь, для 5: 1 ? 0 – истина. Бит А равен «1»
1-ые биты. Для 20: 0 ? 0 – ложь, для 5: 0 ? 0 – ложь. Бит А равен «0»
2-ые биты. Для 20: 1 ? 0 – истина, для 5: 1 ? 0 – истина. Бит А равен «1»
3-и биты. Для 20: 0 ? 0 – ложь, для 5: 0 ? 0 – ложь. Бит А равен «0»
4-ые биты. Для 20: 1 ? 0 – истина, для 5: 0 ? 0 – ложь. Бит А равен «1»
20 10100 ? 0
5 00101 ? 0
А 10101 = 0
Получили А=101012=2110
Ответ: 21
Таким способом задания подобного вида решаются быстро, можно уложиться в рекомендуемые три минуты. Здесь приведено подробное объяснение, но при решении достаточно записать все числа в двоичной записи друг под другом и подбирать биты А в зависимости от удовлетворения равенства или неравенства нулю, и учитывая максимальное или минимальное значение А мы ищем.
1 Задания взяты с сайта
