Задачу Медведихи со стражниками решал через булеву алгебру
Кто помнит карты Карно (таблицы истинности), вот такую я на бумажке набросал...
входные данные 2 бита.
A. Стражник к которому мы подошли лжец? (1-да, 0-нет)
B. Стражник к которому мы подошли стоит возле двери ведущей на эшафот? (1-да,0-нет)
Выходных данных 1 бит Q=(1-да, нет)
Лжец - инвертор, Праведник - буфер. Функция XOR (исключающее или) - есть управляемый инвертор.
A xor B = Q
Задача построить лог. ф-цию. Делающую из двух бит 1.
Насколько мне помнится когда есть два неизвестных, то решается через систему, а если нет возможности, то через О.Д.З.
Ответ стражника (1-да,0-нет) должен заключать в себе информацию о том правильно ли мы выбрали дверь.
Допустим мы решили, что ответ "да" означает, что выходить надо через дверь, возле которой стоит стражник, которому мы задали вопрос. Или идти в противоположную если нам сказали "нет".
Тогда вопрос соответствующий такой функции такой:
"Дверь, возле которой стоит лжец ведет на эшафот?"
Если стражник скажет "да" идем через его дверь, если "нет", то через противоположную.
Можно построить инверсную систему.
Тогда вопрос:
"Дверь, возле которой стоит лжец ведет на свободу?"
Тогда и алгоритм поведения меняется,
если стражник скажет "нет", идем через его дверь, если "да", то меняем дверь.
Также можно поменять "лжец" на "праведник" и тоже изменить алгоритм... Итого имеем четыре вопроса разрешающих ситуацию, и два алгоритма поведения для двух пар этих вопросов.