Форум » Логические уравнения » Задача 115 из ege23.doc » Ответить

Задача 115 из ege23.doc

Сергей.Л: (x1 + x2) * (x1 * x2 --> y1) = 1 (x2 + x3) * (x2 * x3 --> y2) = 1 (x3 + x4) * (x3 * x4 --> y3) = 1 (x4 + x5) * (x4 * x5 --> y4) = 1 (x5 + x6) * (x5 * x6 --> y5) = 1 (x6 + x7) * (x6 * x7 --> y6) = 1 (x7 + x8) * (x7 + y7) = 1 x8 + y8 = 1 Пробую решить "от последнего уравнения" x8 + y8 = 1, отсюда x8y8 = 10,10,11 x8y8=01. Подставляю х8=0 в предпоследнее уравнение нахожу х7, подставляю в предыдущее, нахожу х6 и т.д. Получаю: [pre2]x8 x7 x6 x5 x4 ... 0 ... 1 ... 0 ... 1 ... 0 . 1 1 ... 0 ... 1 1 ... 0 1[/pre2] (если х8=0, то х7=1, а если х7=1, то х6= 0 или 1, а если х6=0, то х5=1, если х6=1, то х5=0 или 1 и т.д. В общем, дерево разветвляется до 22 штук х1. Соответствующие игреки растут так: у8=1 (для х8=0), у7= 0 или 1 (для х7=1), у6= 01 1 (для х6=0 1), у5 = 01 01 1 (для х5=1 0 1) и т.д. В конце у1-ых набирается 34 шт. Число пар определяю как 22 * 34 = 748. Строю такие же деревья для х8у8=10 и 11. В обоих случаях получаю по 1320 пар. Складываю. Сумма = 3388. Правильный ответ = 2358. Что я делаю не так? Заранее спасибо за помощь.

Ответов - 12

Поляков: Это задание, на мой вкус, удобнее решать методом отображений Е.А. Мирончик (по сути это метод динамического программирования). Я опишу решение в несколько нестандартном варианте, без стрелочек, которые вечно путаются. :-) . Рассмотрим первое уравнение, пока только часть x1+x2=1. Пусть из решения предыдущих уравнений у нас есть a подходящих вариантов, при которых x1=0, и b подходящих вариантов, при которых x1=1. Конечно, сейчас a=b=1, но такое предположение облегчит нам вывод формул. Очевидно, что тогда число подходящих вариантов с x2=0 равно b (при x2=0 обязательно обеспечить x1=1), а число вариантов с x2=1 равно a+b (x1 может быть любым). . Теперь подключим вторую часть уравнения (x1*x2 -> y1) = 1. Фактически мы подключаем переменную y1. Итак, по первой части уравнения у нас есть b решений с x2=0, оно удваивается, поскольку y1 может быть равен как 0, так и 1. В то же время, мы имеем a+b решений с x2=1, причем при одновременном выполнении условия x1=0 имеем x1*x2=0, так что (0 -> y1) = 1 и y1 может быть любым. Это даёт общее число решения с x2=1 равное 2a+b. . Начав с a=b=1 и выполняя переход к следующему уравнению по формулам (a,b) <-- (b, 2a+b), находим, что для системы из первых 6 уравнений a=246 (число решений с x7=0) и b=311 (число решений с x7=1). . Пусть x7=0. Из последних двух уравнений получаем x8=1, y7=1 и y8={0, 1}, то есть за счёт y8 количество решений с x7=0 удваивается и становится равно a=2*246 = 492. . При x7=1 предпоследнее уравнение удовлетворяется при любых четырёх комбинациях x8 и y7, то есть, получаем 2*311=622 решения с x8=0 и столько же решений с x8=1. При этом количество решений с x8=1 удваивается за счет произвольного выбора y8={0,1} (из последнего уравнения). В итоге количество решений с x7=1 при добавлении последних двух уравнений вырастет до b=2*311+2*2*311=1866. . Суммируем: 492 + 1866 = 2358. Этот результат подтверждается программой, которая лежит на сайте.

MEA: Еще удобнее будет решать эту систему после изменения - во все уравнения, кроме последнего дописать +y2*0 (меняя индекс на 1). Тогда отображение будет x1, y1 в x2, y2. Система станет самой обычной. Последнее уравнение учесть в последнем столбике. Вместо стрелок можно использовать как матрицу смежности, так и сразу записывать рекуррентные отношения.

Поляков: MEA пишет: Еще удобнее будет решать эту систему после изменения - во все уравнения, кроме последнего дописать +y2*0 (меняя индекс на 1). Это правда упростит дело? А за счет чего?


MEA: Система становится самой обычной - свели задачу к задаче о чайнике :). И анализ последнего уравнения x8+y8=1 - зачеркнуть или сразу поставить 0 в пару 00 последнего столбца. По сути Вы строите переход от x1 к x2 "через" y1. Переход "через" может быть с двойными стрелками. Удобно если в первом уравнении f(x1, x2, x3, y1), а во втором f(x2, x3, x4, y2). В этом случае я строю переход от x1, x2 к x2, x3 через y1. Если количество X и Y совпадает, то последний переход получается от XX к YY

Сергей.Л: Спасибо за подробные ответы, метод Мирончик пока изучаю, но меня интересует ошибка именно в этом решении (методом отображений, конечно же, задача решается в три раза быстрее). Прошу вас помочь именно с ним. Заранее спасибо :)

Поляков: Сергей.Л пишет: меня интересует ошибка именно в этом решении К сожалению, я не владею этим методом, поэтому помочь не смогу.

Сергей.Л: Вы мне помогли вчерашним разъяснением :) Мне сейчас пришла в голову мысль, что рассматриваемое решение - это какая-то модификация метода Мирончик (в обратном направлении). Стало быть, ошибка где-то в реализации. Спасибо за подсказку.

MEA: Когда рисуете дерево, то на очередном шаге попадаете в узел 1 или узел 0, причем много раз. Со всех 1 и со всех 0 будет одинаковое продолжение. Иногда в узлах стоят пары 00, 01, 10, 11. Смысл метода состоит в том, чтобы соединить одинаковые узлы, при этом дерево превращается в ориентированный граф. По сути решается задача про "сколько дорог". Да, можно назвать динамическим программированием, но этот термин ближе для тех случаев, когда уравнения одинаковые - записали формулы и считаем. А если все формулы разные? Значит надо выявить что будет узлами в графе перехода. Можно придумать такую систему, где из 0 и 1 надо переходить на пары, потом опять на 0 и 1 и переход может быть от Х к Y и от пары ХХ в пару XY. Главное понять что на что влияет. И уравнения просчитываются аналогично, причем с разными знаками, и разными скобками - если переменные встречаются по одному разу, то уравнение (количество решений) решается в две строки таблицы, а количество столбцов связано с количеством операций в уравнении. До сегодняшнего дня я не встречала систему, которая не может быть решена стрелками.

dbaxps: Мы инициируем пару перехода не меняя уравнений (x1 + x2) * (x1 * x2 => y1) + y2⊕y2 = 1 (x2 + x3) * (x2 * x3 => y2) + y3⊕y3 = 1 (x3 + x4) * (x3 * x4 => y3) + y4⊕y4 = 1 (x4 + x5) * (x4 * x5 => y4) + y5⊕y5 = 1 (x5 + x6) * (x5 * x6 => y5) + y6⊕y6 = 1 (x6 + x7) * (x6 * x7 => y6) + y7⊕y7= 1 (x7 + x8) * (x7 + y7) + y8⊕y8 = 1 x8 + y8 = 1 Диаграммы м матрица здесь https://mapping-metod.blogspot.com/2019/03/03032019.html

Поляков: dbaxps пишет: Диаграммы м матрица здесь https://mapping-metod.blogspot.com/2019/03/03032019.html На мой взгляд, последняя таблица показывает избыточность - за исключением последнего шага, первая и вторая, а также третья и четвёртая строки одинаковы. Это вызвано тем, что реальной связи через y-переменные между первыми 6-ю уравнениями нет.

MEA: Поляков пишет: На мой взгляд, последняя таблица показывает избыточность - за исключением последнего шага, Да, избыточность, но то, что пишутся пары одинаковых чисел, улавливается моментально. В условиях егэ два одинаковых числа писать нет проблем, почти отдыхаем. Ключевым в добавлении является то, что система не отличается от решаемых ранее. Отдельно последний переход.

dbaxps: Известно , что при использование установок залпового реактивного огня есть определенные издержки, но цель уничтожается мгновенно с вероятностью 99,9%



полная версия страницы