ВВЕДЕНИЕ
Данная курсовая работа представляет собой создание игры «Выдающийся ум» или «Быки и коровы» на языке Пролог с максимальным использованием возможностей языка. Игра развивает аналитическое мышление, интуицию, словарный запас, знание языка.
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
Вы должны написать программу, которая разгадывает секретный код в игре "Выдающийся ум" (игра имеет второе название - "Быки и коровы"). В эту игру играют два игрока. Игрок A выбирает секретный код, представляющий собой последовательность из N десятичных цифр (обычно начинающие игроки выбирают N равным 4, опытные - 5). Игрок B пытается угадать задуманный код и спрашивает игрока A о числе "быков" (число "быков" - количество совпадающих цифр в одинаковых позициях предполагаемого и задуманного кодов) и числе "коров" (число "коров" - количество совпадающих цифр, входящих в предполагаемый и задуманный код, но находящийся в разных позициях). Код угадан, если число быков равно N.
Существует очень простой алгоритм этой игры: вводится некоторый порядок на множестве допустимых правильных предположений; выдвижение очередных предположений учитывает накопленную к этому моменту информацию, и так до тех пор, пока секретный код не будет раскрыт.
Вместо формального определения алгоритма игры обратимся к интуиции читателя: предположения считаются удачными, если ответы на вопросы угадывающего совпадают с ответами, которые были бы даны при разгадке кода.
Если предлагаемый алгоритм запрограммировать, предполагая, что все цифры в коде должны быть различны, то алгоритм будет "играть" в силу опытных игроков: для раскрытия кода из четырех различных цифр ему требуется в среднем 4-6 попыток, наблюдавшийся максимум - 8 попыток. Для вашего задания коды могут быть произвольны, даже с повторяющимися цифрами. Поэтому число попыток приблизительно удваивается.
Человеку стратегию, используемую в алгоритме, применить нелегко, поскольку она требует значительной счетной работы. С другой стороны, управляющая структура Пролога - недетерминированный выбор, моделируемый поиск с возвратами, - представляется идеальной для реализации этого алгоритма.
ОПИСАНИЕ ПРОГРАММЫ
Задача: Разработать систему, позволяющую пользователю играть с компьютером в игру «Выдающийся ум».
Метод решения данной программы является классическим для решения логических задач, и называется «генерация - тестирование». Метод заключается в том, что программа должна сгенерировать вариант решения задачи, затем протестировать этот вариант на достоверность, в противном случае заново повторяется с генерации и последующего тестирования пока при тестировании не получится верный вариант решения.
В этой задаче «генератор» - т.е. та часть программы, которая отвечает за генерирование варианта решения, генерирует различные (все возможные) комбинации числа, состоящего из 4 цифр.
В программе за генерацию отвечают предикаты 'предположение' и 'выбор'.
«Тестер» - т.е. та часть программы, которая отвечает за тестирование достоверности сгенерированного варианта решения, состоит из двух частей.
Первая часть тестера предназначена для проверки того, чтобы сгенерированное решение не повторялось с предыдущими попытками, а заодно, чтобы соответствовало всем ранее введенным пользователем значений быков и коров.
Это предикаты : 'проверка','противоречивое','соответствуют быки и коровы','точное совпадение','общие члены'
Вторая часть тестера проверяет, что введенное пользователем значение не противоречиво и если оно есть решение задачи, если нет, то запоминается пара (сгенерированное число и быки/коровы для этого числа), для того чтобы правильно сгенерировать следующий вариант решения.
Это предикаты; вопрос(Cod) и 'допустимо'.
ПРОГРАММА С КОММЕНТАРИЯМИ
% предикаты, предоставленные в задании не комментирую, так как они прокомментированы в самом задании
'выдающийся ум'(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.
ДОПИСАННАЯ ПРОГРАММА
% предикат "чистка" предназначен для освобождении памяти от результатов предыдущего
% выполнения программы, или предыдущего выполнения правила "выдающейся ум" (предыдущей игры)
% В данном прекате используется стан??дартный предикат retractall(_) который освобождает
% память от добавленных ранее динамических фактов, в данной прорамме мы сохраняем значения
% каждого "хода".
'чистка':-
retractall('запрос'(_,_,_)).
% предикат выбор это по сути "енератор" возможных решений, в нашем случае генератор возможных комбинации загаданного числа
% из списка возможных вариантов (цифры от 0 до 9) он генерирует все возможные варианты этих цифр располагая их
% при этом список %заданной длины
'выбор'([],_):-!.
'выбор'([Вариант|Варианты],Значения):-
'выбор'(Вариант,Значения,ОставшиесяЗначения),
'выбор'(Варианты,ОставшиесяЗначения).
'выбор'(Выбор,[Выбор|Значения],Значения).
'выбор'(Выбор,[Значение|Значения],[Значение|ОставшиесяЗначения]):-
'выбор'(Выбор,Значения,ОставшиесяЗначения).
% сгенерированные возможноые значения числа должны быть проверены на то
% что эти варианты уже не обработаны ранее, и что самое главное что
% учтены все введенные ранее ответы пользователя о количесвах коров и быков
%. Для этого правило "противоречие" проверяет на точное совпадение и общие члены
% точное совпадение это количество совпавших цифр на своем месте т.е. быки
% общие члены это общие цифры но не на своем месте, т.е. коровы
'точное совпадение'([],[],0).
'точное совпадение'([Цифра|OldЦифры],[Цифра|NewЦифры],N+1):-!,
'точное совпадение'(OldЦифры,NewЦифры,N).
'точное совпадение'([_|OldЦифры],[_|NewЦифры],N):-
'точное совпадение'(OldЦифры,NewЦифры,N).
'общие члены'([],_,0).
'общие члены'([OldЦифра|OldЦифры],Код,N+1):-
member(OldЦифра,Код),!,
'общие члены'(OldЦифры,Код,N).
'общие члены'([_|OldЦифры],Код,N):-
'общие члены'(OldЦифры,Код,N).
% допустимо это предикат проверяющий допустимость комбинации быки коровы
% здесь отсеиваются варианты кода к примеру 3 быка и 2 коровы что не может быть т.к. цифр всего 4 и з из них на своем месте
% ниже представлена таблица доспустимых значений
% 0,0 0,1 0,2 0,3 0,4
% 1,0 1,1 1,2 1,3
% 2,0 2,1 2,2
% 3,0 -
% 4,0
'допустимо'(B,C):-
(B < 0 ; C < 0 ; B + C > 4; B=3,C=1), !,
write('Недопустимо!'), nl, false.
'допустимо'(_,_).
% предикат "сообщение" отображает сообщение об успешно найденом решении
сообщение:-
write('Вот так!'), nl.
ТЕСТОВЫЙ ПРИМЕР
Для того чтобы запустить программу нужно исполнить предикат "выдающийся_ум(Cod)".
Затем программа сгенерирует первый вариант решения и спросит сколько в нем быков а сколько коров.
!!!!!!!!!!!!!!!!! (не забываем ставить точки после каждого ввода значения) !!!!!!!!!!!!!!!!!
процедура повторяется пока программа не "отгадает" и не отобразит правильный вариант
Вот протокол исполнения программы для загаданного числа равного 4759:
1 ?- 'выдающийся ум'(Cod).
Гипотеза [1, 2, 3, 4]
Сколько быков?
|: 0.
Сколько коров?
|: 1.
Гипотеза [2, 5, 6, 7]
Сколько быков?
|: 0.
Сколько коров?
|: 2.
Гипотеза [3, 6, 5, 8]
Сколько быков?
|: 1.
Сколько коров?
|: 0.
Гипотеза [4, 6, 7, 9]
Сколько быков?
|: 2.
Сколько коров?
|: 1.
Гипотеза [4, 7, 5, 9]
Сколько быков?
|: 4.
Сколько коров?
|: 4.
Вот так!
Cod = [4, 7, 5, 9]
Заключение
В результате мною была разработана программа-игра "Быки и коровы". Для этого было проведено несколько этапов.
На первом этапе была разработана функционально-структурная схема.
На втором этапе строится структурные схемы для написания текста программы (третий этап).
Также было проведено тестирование. Они показали, что программа функционирует верно.
СПИСОК ЛИТЕРАТУРЫ
1. Зюзьков «Пролог в примерах и задачах». – Томск.: «КУРСИВ», 2001. – 280 стр.
2. Братко И. «Программирование на языке ПРОЛОГ для искусственного интеллекта». – М.: «МИР», 1990. – 560 с.
3 Батырь А.Ю., Герр Р.Г. Компьютер обретает разум Пер. с англ. - М.: Мир, 1990. - 238 с.: ил.
4 Малпас Дж. Реляционный язык Пролог и его применение: Пер. с англ. /Под редакцией В.Н. Соболева. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 464 с. |
Главная
Каталог файлов
