3.2.1 Задача о холостяке
Условие задачи. Для холостяка характерно, что он – мужчина и что он не женат.
Введем факты. Известно, что есть Федя и Вася. И Федя –женат.
Сочиним программу
мужчина(федя).
мужчина(вася).
женат(федя).
Условие «неженатости» запишем с помощью встроенного предиката отрицания.
Его запись может быть двоякой: или с помощью слова «not» или последовательностью двух символов «\+». Оба написания равнозначны, но второе считается более(!) правильным.
холостяк(X) :- мужчина(X),(\+ женат(X)).
Позадаём вопросы.
?- холостяк(Kто).
Kто = вася ;
No
?- холостяк(федя).
No
?- холостяк(вася).
Yes
?- холостяк(никифор).
No
Никифора – просто нет!
Запрос с отрицанием
?- not(женат(федя)).
No
?- \+(женат(федя)).
No
?- not(женат(коля)).
Yes
3.2.2 Разберём задачу в которой реализовано сложное правило.
Есть три студента. Про них известно, кто из них посещает лекции, и кто - сколько сдал лабораторных работ.
В задаче считается, что неуспевающий студент – если он не посещает лекции или количество сданных работ у него менее четырех.
Надо указать пофамильно, кто неуспевающий.
сдал_работ(пельше,5).
сдал_работ(косыгин,3).
сдал_работ(устинов,4).
посещает_лекции(косыгин).
посещает_лекции(пельше).
не_успевающий_студент(Fамилия):-
(\+ (посещает_лекции(Fамилия)));
сдал_работ(Fамилия,Kоличество_сданных_лаб),
Kоличество_сданных_лаб < 4.
?- не_успевающий_студент(X).
X = косыгин ;
No
Вот что показывает работа trace
[trace] 45 ?- не_успевающий_студент(X).
Call: (7) не_успевающий_студент(_G489) ? creep
Call: (8) посещает_лекции(_G489) ? creep
Exit: (8) посещает_лекции(косыгин) ? creep
Call: (8) сдал_работ(_G489, _L181) ? creep
Exit: (8) сдал_работ(пельше, 5) ? creep
^ Call: (8) 5<4 ? creep
^ Fail: (8) 5<4 ? creep
Redo: (8) сдал_работ(_G489, _L181) ? creep
Exit: (8) сдал_работ(косыгин, 3) ? creep
^ Call: (8) 3<4 ? creep
^ Exit: (8) 3<4 ? creep
Exit: (7) не_успевающий_студент(косыгин) ? creep
X = косыгин ;
Redo: (8) сдал_работ(_G489, _L181) ? creep
Exit: (8) сдал_работ(устинов, 4) ? creep
^ Call: (8) 4<4 ? creep
^ Fail: (8) 4<4 ? creep
Fail: (7) не_успевающий_студент(_G489) ? creep
No
В заключении обсуждения механизма поиска решений решим классическую логическую задачу.
3.3 Задача о Ханойской башне
Смысл этой известной задачи в том, что нужно переместить N(конечное число) произвольных исходных дисков с крайнего левого шеста на крайний правый. В процессе решения любой верхний диск можно насадить на любой штырек, но с одним ограничением – если на этом штырька уже есть диск (а может быть и не один), то диск, который кладется сверху, должен быть меньше. Так сохраняется форма пирамиды
Следующая диаграмма изображает начальную загруженность штырьков для N=3 дисков.
Программа, которая решает
эту задачу, состоит из
двух предложений.
X Z Y
Первое правило делает самое главное действие - перемещение одного диска между двумя штырьками (с X на Y). Поскольку третий штырек в таком действии не используется – он «все равно какой», т.е. его можно обозвать анонимной переменной.
Здесь же добавлен комментарий, чтобы «воочию увидеть» осуществляемую перестановку
move(1,X,Y,_) :-
write(' Передвигаю верхний диск с <'),
write(X), write('> на <'),
write(Y), write('>'),
nl.
Как только понятно, что делать с одним диском с остальными дисками действия определятся рекурсивно для произвольного N.
move(N,X,Y,Z) :-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
Почему нельзя сделать проще, например, определить move1(X,Y)? вместо move(1,X,Y,_) ? Все дело в рекурсивности алгоритма.
При вызове, например, move(3, левый,правый,средний) происходит рекурсивный вызов этой же процедуры, но с уменьшением параметра N(=3) до 1. Далее, при M=1 должно состояться «реальное перемещение» ровно одного диска в заданном направлении, т.е. вызов move(1,X,Z,Y), чему удовлетворяет первое утверждение, т.е. move(1,X,Y,_) НО не move1(X,Y) !!! (Которое, просто, никогда не сможет быть использовано)
Далее приводится работа программы для случая N=3.
?- move(3, левый,правый,средний).
Передвигаю верхний диск с <левый> на <правый>
Передвигаю верхний диск с <левый> на <средний>
Передвигаю верхний диск с <правый> на <средний>
Передвигаю верхний диск с <левый> на <правый>
Передвигаю верхний диск с <средний> на <левый>
Передвигаю верхний диск с <средний> на <правый>
Передвигаю верхний диск с <левый> на <правый>
Yes
Давайте разберем на примере работу второго предложения для N=3, X= left, Y= right, и Z= center
Итак, чтобы сделать
move(3,left,right,center)
надо сделать три вызова
move(2,left,center,right) (2A) move(1,left,right,center) move(2,center,right,left) (2B)
В свою очередь для N=2 обращение:
move(2,left,center,right) (2A)
перейдет в три вызова
move(1,left,right,center) move(1,left,center,right) move(1,right,center,left)
Движение одного диска пока опускаем, а
move(2,center,right,left) (2B)
станет
move(1,center,left,right) move(1,center,right,left) move(1,left,right,center)
А теперь, соединив всё вместе можно "видеть" решение, в виде цели, сгенерированной Прологом.
Получается, можно сделать
move(3,left,right,center) если
move(1,left,right,center) и move(1,left,center,right) и (2A) move(1,right,center,left) и --------------------------- move(1,left,right,center) и --------------------------- move(1,center,left,right) и move(1,center,right,left) и (2B) move(1,left,right,center)
Этот пример хорошо иллюстрирует мощность и возможности языка Пролог.