Автор | Сообщение |
|
Отправлено: 02.01.18 18:13. Заголовок: Решение масками № 383, 382, 379
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
[только новые]
|
|
|
| Администратор
|
Сообщение: 1563
|
|
Отправлено: 02.01.18 18:17. Заголовок: 137 пишет: И ЧТО НЕ ..
137 пишет: Приведите, пожалуйста, ссылку на источник, где описывается алгоритм решения масками и доказывается его правильность. Потом будет иметь смысл что-то обсуждать.
|
|
|
|
Отправлено: 02.01.18 18:27. Заголовок: Бралось из теории eg..
Бралось из теории ege18 Р-22. Решение (4 способ, М.В. Кузнецова ) с-но и способ Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург) о том-же
|
|
|
|
| Администратор
|
Сообщение: 1564
|
|
Отправлено: 02.01.18 18:31. Заголовок: 137 пишет: Бралось и..
137 пишет: цитата: | Бралось из теории ege18 Р-22. Решение (4 способ, М.В. Кузнецова ) с-но и способ Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург) о том-же |
|
По-видимому, эти подходы имеют свои ограничения, на которые вы и нарвались. Рекомендую посмотреть вот эту статью. По крайней мере, там все доказано и я не видел еще ни одной задачи на битовые операции, которая этим методом не решалась бы "на ура".
|
|
|
|
Отправлено: 03.01.18 00:56. Заголовок: Спасибо за статью. ..
Спасибо за статью. Хочется иметь именно универсальный метод, который работает 100% "Перерешиваю" все задания по Здвижковой. "На ура" пока не все получается. (Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.) (X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0) Ищем А min для ложности формулы. В обозначениях из теории, выражение максимально упрощается до A∧¬Z 35∧Z 52 ... Упрощение по Здвижковой должно привести к одному из 4-х видов импликации без инверсии, чего не получается в данном случае (у меня). напрашивается посчитать or для ¬Z 35∧Z 52 , но в теории нет случая с инверсией - т.е. нельзя.
|
|
|
|
| Администратор
|
Сообщение: 1565
|
|
Отправлено: 03.01.18 12:56. Заголовок: 137 пишет: (Задание ..
137 пишет: цитата: | (Задание 18 ЕГЭ по информатике 2017 ФИПИ вариант 9 (Крылов С.С., Чуркина Т.Е.) |
|
Как я понял, нужно найти минимальное A, при котором выражение ложно. Давайте приведём к стандартной задаче с 1 в правой части - возьмем инверсию от обеих частей. Тогда получаем not(A* not Z32 * Z52) = 1 not A + Z35 + not Z52 = 1 Тут левую часть можно свести к стандартной импликации без инверсий (A*Z52) -> Z35 = 1. Далее все стандартно, ответ - 3 (любое число, где установлены биты 0 и 1, которые есть в числе 35, но нет в 52).
|
|
|
|
Отправлено: 08.01.18 11:13. Заголовок: СПАСИБО!..
СПАСИБО!
|
|
|
|