Одесский национальный университет им. И.И.Мечникова Министерство науки и образования Украины
Лабораторная работа №4
по курсу «Специализированные языки программирования»
выполнил студент III курса гр. МОКС
Свиридов Артём
Одесса 2012
Цель работы: приобретение навыков разработки программ, решающих логические задачи с помощью Пролога.
Постановка задачи.
Разработать программу, реализующую задание:
Задача о переливании воды 2
Имеются три бочонка вместимостью 6 вёдер, 3 ведра и 7 вёдер. В первом и третьем содержится соответственно 4 и 6 вёдер кваса. Требуется, пользуясь только этими тремя бочонками, разлить квас поровну (т.е. в первом бочонке – 5 вёдер и в третьем – 5 вёдер).
Код программы на Visual Prolog 7.3:
implement main
open core, console, string
constants
className = "main". classVersion = "".
clauses
classInfo(className, classVersion).
domains
list = integer*. symbollist=symbol*.
class facts
barrel: (integer,integer,integer).
class predicates
decant : (integer, integer, integer, integer, integer) procedure(i,i,i,o,o).
solve : (integer, integer, integer, integer, integer, integer, integer, integer, integer, integer) determ(i,i,i,i,i,i,i,i,i,i).
find : (integer, integer, integer) determ(i,i,i).
do_it : (integer, integer, integer, integer, integer, integer, integer, integer, integer) procedure(i,i,i,i,i,i,i,i,i).
clauses barrel(4,0,6).
decant(X,Y,YL,X-(YL-Y),YL) :- X > YL-Y, !. decant(X,Y,_,0,Y+X).
find(X,Y,Z) :- barrel(X,Y,Z), !, fail. find(_,_,_).
solve(R1,R2,R3,_,_,_,_,R1,R2,R3) :- !. /*x -> y */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- X>0, Y<YL, decant(X,Y,YL,X1,Y1), write(N,": ",X1," ",Y1," ",Z), _ = readLine(), find(X1,Y1,Z), assert(barrel(X1,Y1,Z)), solve(X1,Y1,Z,XL,YL,ZL,N+1,R1,R2,R3), !.
/*y -> z */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- Y>0, Z<ZL, decant(Y,Z,ZL,Y1,Z1), write(N,": ",X," ",Y1," ",Z1), _ = readLine(), find(X,Y1,Z1), assert(barrel(X,Y1,Z1)), solve(X,Y1,Z1,XL,YL,ZL,N+1,R1,R2,R3), !.
/*z -> x */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- Z>0, X<XL, decant(Z,X,XL,Z1,X1),
write(N,": ",X1," ",Y," ",Z1), _ = readLine(), find(X1,Y,Z1), assert(barrel(X1,Y,Z1)), solve(X1,Y,Z1,XL,YL,ZL,N+1,R1,R2,R3), !.
/*x -> z */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- X>0, Z<ZL, decant(X,Z,ZL,X1,Z1), write(N,": ",X1," ",Y," ",Z1), _ = readLine(), find(X1,Y,Z1), assert(barrel(X1,Y,Z1)), solve(X1,Y,Z1,XL,YL,ZL,N+1,R1,R2,R3), !.
/*z -> y */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- Z>0, Y<YL, decant(Z,Y,YL,Z1,Y1), write(N,": ",X," ",Y1," ",Z1), _ = readLine(), find(X,Y1,Z1), assert(barrel(X,Y1,Z1)), solve(X,Y1,Z1,XL,YL,ZL,N+1,R1,R2,R3), !.
/*y -> x */
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) :- Y>0, X<XL, decant(Y,X,XL,Y1,X1), write(N,": ",X1," ",Y1," ",Z), _ = readLine(), find(X1,Y1,Z), assert(barrel(X1,Y1,Z)), solve(X1,Y1,Z,XL,YL,ZL,N+1,R1,R2,R3), !.
solve(_,_,_,_,_,_,_,_,_,_) :- write("Неудачный путь"), nl, nl, fail.
do_it(X,Y,Z,XL,YL,ZL,R1,R2,R3) :- write("0: ",X," ",Y," ",Z), _ = readLine(), solve(X,Y,Z,XL,YL,ZL,1,R1,R2,R3), !.
do_it(_,_,_,_,_,_,_,_,_) :- write("Решение невозмоно").
clauses run():-
console::init(), do_it(4,0,6,6,3,7,5,0,5), console::clearInput(), _=readline().
end implement main
goal mainExe::run(main::run).
Программа позволяет решать не только в точности данную задачу, но и похожие задачи с другими значениями вместимости бочонков, количеством кваса и распределением, которого нужно достигнуть. Но количество бочонков – обязательно три.
do_it(X,Y,Z,XL,YL,ZL,R1,R2,R3) – функция, решающая задачу и выводящая решение на экран. X, Y, Z – квас, который в данный момент находится в соответствующих бочонках. XL, YL, ZL – вместимость соответствующих бочонков. R1, R2, R3 – распределение, которого требуется достичь.
Например, для первоначальной задачи функция будет выглядеть do_it(4,0,6,6,3,7,5,0,5).
Алгоритм:
Функция solve во время каждого вызова пытается перелить квас из одного бочонка в другой. Пара бочонков выбирается как первая пара из очереди (X->Y, Y->Z, Z->X, X->Z, Z->Y, Y->X), между бочонками которой можно осуществить перелив.
Создаётся внутренняя база данных фактов типа barrel(X,Y,Z), в которую записываются все варианты расположения кваса в бочонках, достигнутые по ходу программы. В случае, если какое-либо расположение повторилось, программа
возвращается на одну позицию назад, и пробует найти новое расположение. Так до тех пор, пока не будет достигнуто требуемое расположение.
Функции программы:
decant(X,Y,YL,X1,Y1) – переливает воду из одного бочонка в другой, где X, Y – первоначальное количество вёдер в бочонках, YL – вместимость второго бочонка, X1, Y1 – результирующее количество вёдер в бочонках.
find(X,Y,Z) – ищет, есть ли среди фактов barrel данное расположение; если есть, возвращает fail.
solve(X,Y,Z,XL,YL,ZL,N,R1,R2,R3) – главная функция программы. Все аргументы аналогичны аргументам do_it, за исключением N – номер попытки перелить квас.
Сначала функция проверяет, равны ли первые три аргумента последним трём (то есть требуемое расположение достигнуто), и в этом случае она прерывается.
Иначе она пытается перелить квас из первого возможного бочонка в другой. Когда такие бочонки найдены, вызывается decant, новое расположение кваса выводится на экран.
Далее проверяется, существует ли такое расположение. Если не существует – новое расположение вводится в базу данных с помощью assert. Если существует, find возвращает fail.
После проверки функция рекурсивно вызывается уже для нового расположения. Если эта функция вернула fail – значит, этот путь неверен.
В случае fail функция ищет новую доступную пару бочонков.
Если первоначальная функция solve вернула fail – значит, решить задачу невозможно.
Результат работы программы:
Первоначальная задача
Другие задачи
do_it(4,0,6,6,3,7,6,0,4)
do_it(3,2,3,5,2,4,4,2,2)
Вывод
В данной лабораторной работе были получены необходимые навыки разработки программ, решающих логические задачи с помощью в Visual Prolog 7.3.