Если предлагаемый алгоритм запрограммировать, предполагая, что все цифры в коде должны быть различны, то алгоритм будет "играть" в силу опытных игроков: для раскрытия кода из четырех различных цифр ему требуется в среднем 4-6 попыток, наблюдавшийся максимум - 8 попыток. Для вашего задания коды могут быть произвольны, даже с повторяющимися цифрами. Поэтому число попыток приблизительно удваивается.
Человеку стратегию, используемую в алгоритме, применить нелегко, поскольку она требует значительной счетной работы. С другой стороны, управляющая структура Пролога - недетерминированный выбор, моделируемый поиск с возвратами, - представляется идеальной для реализации этого алгоритма.
Приведем основную часть программы.
'выдающийся ум'(Cod):-
'чистка',
'предположение'(Cod),
'проверка'(Cod),
сообщение.
'предположение'([X1,X2,X3,X4]):-
'выбор'([X1,X2,X3,X4], [1,2,3,4,5,6,7,8,9,0]).
% проверка предложенной гипотезы
'проверка'(Cod):-
not 'противоречивое'(Cod),
'вопрос'(Cod).
'противоречивое'(Cod):-
'запрос'(OldCod,B,C), % B -быки, C - коровы
not 'соответствуют быки и коровы'(OldCod,Cod,B,C).
'соответствуют быки и коровы'(OldCod,Cod,B,C):-
'точное совпадение'(OldCod,Cod,N1),
B=:=N1, % правильное число быков
'общие члены'(OldCod,Cod,N2),
C=:=N2-B. % правильное число коров
% оценка гипотезы
вопрос(Cod):-
repeat,write('Гипотеза '),write(Cod),nl,
write('Сколько быков?'),nl,
read(B),nl,
write('Сколько коров?'),nl,
read(C),nl,
'допустимо'(B,C),!,
assert('запрос'(Cod,B,C)),
B=:=4.
Спрашивающая процедура 'предположение'(Cod), которая действует как генератор, использует процедуру выбора 'выбор'([X1,X2,X3,X4], [1,2,3,4,5,6,7,8,9,0]) для выбора списка из четырех десятичных цифр.
Процедура 'проверка'(Cod) испытывает предложенную гипотезу Cod. Сначала проверяется, что Cod не противоречит всем ранее полученным ответам (т. е. непротиворечив с каждым из них), затем задается вопрос о числе быков и коров в предположении Cod. Кроме того, процедура вопрос(Cod) управляет циклом "образовать и проверить", который завершается только тогда, когда число быков равно 4, что является признаком отыскания правильного хода. |
Главная
Каталог файлов
