Форум » Логические выражения » Решение масками № 383, 382, 379 » Ответить
Решение масками № 383, 382, 379
137: 383 Определите наибольшее натуральное число A, такое что выражение (X & A ≠ 0) → ((X & 14 = 0) → (X & 75 ≠ 0)), (A = 0) V (14 ≠ 0) V (75 ≠ 0)=Ист, т.е. A = 0 даже в том случае, когда (14 = 0) V (75 =0) Решаем масками 14 =1110 Маска14= 000х - при этих значениях 14=0 75 =1001011 Маска75=0хх0х00 - при этих значениях 75=0 Объединяя маски получим 0000000 - т.к. маску 14 мы должны дополнить незначащими нулями для поразрядной конъюнкции. В этом случае максимальное А - 1111111=127. Ответ 79, как на сайте получим только в том случае, если маска для 14 не будет дополнена 000. Аналогично в задаче 382 A ≠ 0 даже в том случае, когда (29≠0)^(9 = 0) 29 =11101, 29≠0, Маска 29=111х1, 9 =1001, 9 = 0, Маска 9= 0хх0 0хх0 111х1 Мобщ=101х0 Аmin =10100≠0=20. Но!!! Только в том случае, если 9 не дополняется незначащими нулями при конъюнкции масок. Иначе общая маска 001х0 и Аmin =00100≠0=4 В других задачах также. Если решить все задачи масками ответы сходятся только в тех случаях, если кол-во разрядов одинаково, хотя по теории можно дополнять число незначащими нулями для поразрядной конъюнкции. И ЧТО НЕ ТАК???
Ответов - 6
Поляков: 137 пишет: И ЧТО НЕ ТАК??? Приведите, пожалуйста, ссылку на источник, где описывается алгоритм решения масками и доказывается его правильность. Потом будет иметь смысл что-то обсуждать.
137: Бралось из теории ege18 Р-22. Решение (4 способ, М.В. Кузнецова ) с-но и способ Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург) о том-же
Поляков: 137 пишет: Бралось из теории ege18 Р-22. Решение (4 способ, М.В. Кузнецова ) с-но и способ Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург) о том-же По-видимому, эти подходы имеют свои ограничения, на которые вы и нарвались. Рекомендую посмотреть вот эту статью. По крайней мере, там все доказано и я не видел еще ни одной задачи на битовые операции, которая этим методом не решалась бы "на ура".
137: Спасибо за статью. Хочется иметь именно универсальный метод, который работает 100% "Перерешиваю" все задания по Здвижковой. "На ура" пока не все получается. (Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.) (X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0) Ищем А min для ложности формулы. В обозначениях из теории, выражение максимально упрощается до A∧¬Z35∧Z52 ... Упрощение по Здвижковой должно привести к одному из 4-х видов импликации без инверсии, чего не получается в данном случае (у меня). напрашивается посчитать or для ¬Z35∧Z52 , но в теории нет случая с инверсией - т.е. нельзя.
Поляков: 137 пишет: (Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.) Как я понял, нужно найти минимальное A, при котором выражение ложно. Давайте приведём к стандартной задаче с 1 в правой части - возьмем инверсию от обеих частей. Тогда получаем[pre2] not(A* not Z32 * Z52) = 1 not A + Z35 + not Z52 = 1[/pre2]Тут левую часть можно свести к стандартной импликации без инверсий[pre2](A*Z52) -> Z35 = 1.[/pre2]Далее все стандартно, ответ - 3 (любое число, где установлены биты 0 и 1, которые есть в числе 35, но нет в 52).
137: СПАСИБО!
полная версия страницы