Отправлено: 01.03.19 21:30. Заголовок: Задача 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 и т.д.
Получаю:

x8    x7    x6    x5     x4 ... 
 0 ... 1 ... 0 ... 1 ... 0    
              .          1 
             1 ... 0 ... 1 
                   1 ... 0 
                         1

(если х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.

Что я делаю не так?
Заранее спасибо за помощь.

 Отправлено: 02.03.19 20:07. Заголовок: Это задание, на мой ..

Это задание, на мой вкус, удобнее решать методом отображений Е.А. Мирончик (по сути это метод динамического программирования). Я опишу решение в несколько нестандартном варианте, без стрелочек, которые вечно путаются. :-)
.
Рассмотрим первое уравнение, пока только часть 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. Этот результат подтверждается программой, которая лежит на сайте.

 Отправлено: 02.03.19 20:34. Заголовок: Еще удобнее будет ре..

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

 Отправлено: 02.03.19 20:44. Заголовок: MEA пишет: Еще удобн..

MEA пишет:

цитата:

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

Это правда упростит дело? А за счет чего?

 Отправлено: 02.03.19 21:09. Заголовок: Система становится с..

Система становится самой обычной - свели задачу к задаче о чайнике :). И анализ последнего уравнения 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

 Отправлено: 02.03.19 22:08. Заголовок: Спасибо за подробные..

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

 Отправлено: 03.03.19 10:55. Заголовок: Сергей.Л пишет: меня..

Сергей.Л пишет:

цитата:

меня интересует ошибка именно в этом решении

К сожалению, я не владею этим методом, поэтому помочь не смогу.

 Отправлено: 03.03.19 15:59. Заголовок: Вы мне помогли вчера..

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

 Отправлено: 03.03.19 16:21. Заголовок: Когда рисуете дерево..

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

 Отправлено: 03.03.19 20:39. Заголовок: Еще один урок от МЕА

Мы инициируем пару перехода не меняя уравнений
(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

 Отправлено: 04.03.19 08:20. Заголовок: dbaxps пишет: Диагра..

dbaxps пишет:

цитата:

Диаграммы м матрица здесь https://mapping-metod.blogspot.com/2019/03/03032019.html

На мой взгляд, последняя таблица показывает избыточность - за исключением последнего шага, первая и вторая, а также третья и четвёртая строки одинаковы. Это вызвано тем, что реальной связи через y-переменные между первыми 6-ю уравнениями нет.

 Отправлено: 04.03.19 10:01. Заголовок: Поляков пишет: На м..

Поляков пишет:

цитата:

На мой взгляд, последняя таблица показывает избыточность - за исключением последнего шага,

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

 Отправлено: 04.03.19 13:16. Заголовок: Мое частное мнение

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