Форум » Логические уравнения » решение битовыми цепочками » Ответить
решение битовыми цепочками
cabanov.alexey: По поводу методов решения логических систем для меня остаётся открытым вопрос - как решать вот такие системы битовыми цепочками. ИМХО, задачи из реального ЕГЭ заточены больше под метод отображений.
Ответов - 4
MEA: cabanov.alexey пишет: По поводу методов решения логических систем Думаю, что область применения метода отображений шире, чем других методов
Поляков: cabanov.alexey пишет: как решать вот такие системы битовыми цепочками. Это задача "под метод отображений".задачи из реального ЕГЭ заточены больше под метод отображений. Это не задача реального ЕГЭ, это задача Статграда. Думаю, что область применения метода отображений шире, чем других методов Несомненно. Как правило, битовыми цепочками хорошо решаются системы, где есть иксы и игреки. Они сводятся к трем уравнениям: в одном только иксы, в другом - только игреки, а третье - уравнение связи между ними.
MEA: Поляков пишет: Как правило, битовыми цепочками хорошо решаются системы, где есть иксы и игреки. Они сводятся к трем уравнениям: в одном только иксы, в другом - только игреки, а третье - уравнение связи между ними. И этот случай стрелками тоже легко
Поляков: cabanov.alexey пишет: как решать вот такие системы битовыми цепочками В принципе, можно и битовыми цепочками. 1) Всего комбинаций 2^10. Уравнения запрещают комбинации 1->0, это может быть, когда в цепочке встречаются последовательности 1100 и 0000, начинающиеся с нечётных позиций. У нас есть, таким образом, 5 пар. 2) Пусть цепочка заканчивается на пару 00 (это 5-я пара). Слева от нее может быть 4-я пара - одна из двух: 01 или 10, остальные запрещены. Таким образом, 4-я пара не вносит ограничений на предыдущую, потому что она не 00. 3) Пусть последняя пара не 00, а одна из трёх оставшихся: 01, 10 или 11. Эти пары не ограничивают предыдущую, так как они не 00. 4) В итоге количество цепочек для N пар, обозначаемое KN, находится по рекуррентной формуле KN = 2KN-2 + 3KN-1. Начальные значения: K0=1, K1=4. Получаем K5 = 634.
полная версия страницы