Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Шумихин / Шумихин / Отчёт_Лаб#4

.pdf
Скачиваний:
13
Добавлен:
20.05.2015
Размер:
221.52 Кб
Скачать

Одесский национальный университет им. И.И.Мечникова Министерство науки и образования Украины

Лабораторная работа №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.