Лада Есакова, преподаватель информатики и математики, автор книги "Информатика. Полный курс подготовки к ЕГЭ".
Добрый день!
Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.
Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.
Давайте порешаем задачи.
«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение
(X & 56 ≠0)→((X & 48=0)→(X & A ≠0)).»
Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х56, в коротком виде. Первое уравнение принимает вид . Нам нужно найти наименьшее натуральное А.
Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.
Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)
На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.
С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.
На что мне надо умножить 48, чтобы получились одни нули?
У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно
И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56
Дальше может стоять что угодно. Все такие X являются решением этого уравнения.
Второе уравнение говорит, что все такие X (001…) нужно умножить на А и не получить ноль.
На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.
Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.
А это значит 8 в десятичной системе.
Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Поразрядная конъюнкция задачи 3» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.
Публикация обновлена: 08.03.2023