Разработка программы с использованием языка логического программирования Prolog

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра вычислительной техники

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОМУ ПРОЕКТУ ПО ДИСЦИПЛИНЕ

" ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ"

Тема:

Разработка программы с использованием языка логического программирования Prolog

Студент:

Гайфулин И. Р.

Преподаватель:

Новицкая Ю. В.

Новосибирск 2011 г.

Задание

Разработать программу для поиска пути в лабиринте.

Предусмотреть возможность задания входа и выхода, наглядное представление найденных решений.

Назначение программного продукта

Данный программный продукт предназначен для выполнения развлекательной функции (демонстрация различных вариантов движения по лабиринту).

Описание данных

DOMAINS

file = fop

Данный домен предназначен для оперирования файлами.

line = integer*

Данный домен предназначен для оперирования списком чисел.

matrix = line*

Данный домен предназначен для оперирования матрицей чисел.

PREDICATES

getline (integer, line, line)

Данный предикат предназначен для получения списка чисел из файла (строки чисел).

getlines (integer, integer, matrix, matrix)

Данный предикат предназначен для получения матрицы чисел (лабиринта) из файла.

getmatrix (integer, matrix)

Данный предикат предназначен для получения лабиринта из файла, это обертка для вышеописанных функций.

reverse (line, line, line)

Данный предикат предназначен реверсии списка.

reverselines (integer, matrix, matrix, matrix)

Данный предикат предназначен для реверсии матрицы.

getelemfromline (line, integer, integer)

Данный предикат предназначен для получения элемента, стоящего на определенной позиции, из списка чисел.

getelem (matrix, integer, integer, integer)

Данный предикат предназначен для элемента из матрицы чисел.

markelemfromline (integer, line, integer, line)

Данный предикат предназначен для изменения элемента в списке.

markelem (integer, matrix, integer, integer, matrix)

Данный предикат предназначен для изменения элемента в матрице чисел.

step (matrix, integer, integer, integer, integer, integer)

Данный предикат предназначен для произведения попытки хода.

operate (integer, matrix, integer, integer, integer, integer, integer)

Данный предикат предназначен для обработки лабиринта и вывода путей.

printline (line, integer)

Данный предикат предназначен для вывода строки с числами в файл.

print (matrix, integer, integer)

Данный предикат предназначен для вывода матрицы в файл.

Main

Это главный предикат, обертка для остальных предикатов.

Repeat

Данный предикат предназначен для организации цикла.

case (matrix, integer, integer)

Данный предикат предназначен для оперирования перебором случаев, используется в интерактивном меню.

Описание методов решения

Метод решения представляет собой перебор всех возможных вариантов ходов из начальной клетки в конечную, при условии, что клетка, в которую совершается перемещение, не является уже пройденной в данном варианте прохода и находится в пределах лабиринта. Ходы будут совершаться до тех пор, пока программа не попадет в конечную клетку.

Описание программы

Программа работает следующим образом:

1. Из задаваемого пользователем входного файла считывается структура лабиринта, который задается следующим образом:

Здесь первое число означает количество строк и столбцов, единица означает «стену», а 0 — свободную клетку. Сначала считывается первая строка, затем вторая, и т. д.

2. Считываются координаты клетки отправления и клетки назначения.

3. Выполняется попытка хода в одну из 8 возможных сторон.

4. Клетка проверяется на пустоту.

5. Если такая клетка не пуста, то попытка считается неудовлетворительной, и перебор продолжается.

6. Если клетка пуста, то она отмечается положительным числом, которое означает номер клетки в возможном варианте пути.

7. Если клетка является конечной, то лабиринт выводится в текстовый файл lab. txt в форме матрицы, в которой наглядным образом виден путь от начальной клетки до конечной. Затем происходит откат к первой возможной точке возврата (переход к 3 пункту).

8. Если клетка не является конечной, то переходим к 3 пункту.

9. Если возможных вариантов больше нет, то программа завершает поиск возможных вариантов.

Описание пользовательского интерфейса

Пользовательский интерфейс включает в себя диалог с пользователем, в ходе которого запрашивается имя файла, содержащего лабиринт, координаты клетки отправления и клетки назначения. Вывод путей производится в текстовый файл «lab. txt».

логическое программирование prolog программа

· Новицкая Ю. В. «Основы логического и функционального программирования» Электронное учебное пособие.

Приложение

Листинг программы.

DOMAINS

file = fop

line = integer*

matrix = line*

PREDICATES

getline (integer, line, line)

getlines (integer, integer, matrix, matrix)

getmatrix (integer, matrix)

reverse (line, line, line)

reverselines (integer, matrix, matrix, matrix)

getelemfromline (line, integer, integer)

getelem (matrix, integer, integer, integer)

markelemfromline (integer, line, integer, line)

markelem (integer, matrix, integer, integer, matrix)

step (matrix, integer, integer, integer, integer, integer)

operate (integer, matrix, integer, integer, integer, integer, integer)

printline (line, integer)

print (matrix, integer, integer)

main

repeat

case (matrix, integer, integer)

CLAUSES

getline (0, Line, Line): ;

!.

getline (Cnt, OldList, Line): ;

readint (Value),

Temp = [Value | OldList],

NewCnt = Cnt — 1, getline (NewCnt, Temp, Line).

getlines (0, _, NewMatrix, NewMatrix): ;

!.

getlines (Cnt, MSize, OldMatrix, NewMatrix): ;

getline (MSize, [], Line),

Temp = [Line | OldMatrix],

NewCnt = Cnt — 1, getlines (NewCnt, MSize, Temp, NewMatrix).

getmatrix (MSize, OutputMatrix): ;

readint (MSize),

getlines (MSize, MSize, [], OutputMatrix).

reverse ([], OutputList, OutputList): ;

!.

reverse ([H | T], List, OutputList): ;

NewList = [H | List],

reverse (T, NewList, OutputList).

reverselines (0, _, ModifiedMatrix, ModifiedMatrix): ;

!.

reverselines (Cnt, [H | T], TmpMatrix, ModifiedMatrix): ;

reverse (H, [], ReversedLine),

NewMatrix = [ReversedLine | TmpMatrix],

NewCnt = Cnt — 1, reverselines (NewCnt, T, NewMatrix, ModifiedMatrix).

getelemfromline ([H | T], 1, H): ;

!.

getelemfromline ([H | T], J, Elem): ;

NewJ = J — 1, getelemfromline (T, NewJ, Elem).

getelem ([H | T], 1, J, Elem): ;

!, getelemfromline (H, J, Elem).

getelem ([H | T], I, J, Elem): ;

NewI = I — 1, getelem (T, NewI, J, Elem).

markelemfromline (Mark, [H | T], 1, [Mark | T]): ;

!.

markelemfromline (Mark, [H | T], J, [H | ModifiedLine]): ;

NewJ = J — 1, markelemfromline (Mark, T, NewJ, ModifiedLine).

markelem (Mark, [H | T], 1, J, [NewLine | T]): ;

!, markelemfromline (Mark, H, J, NewLine).

markelem (Mark, [H | T], I, J, [H | NewMatrix]): ;

NewI = I — 1, markelem (Mark, T, NewI, J, NewMatrix).

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX,

ToY = FromY + 1, ToY <= MSize,

getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX,

ToY = FromY — 1, ToY >= 0, getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX + 1, ToY = FromY + 1, ToX <= MSize,

ToY <= MSize,

getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX + 1, ToY = FromY,

ToX <= MSize,

getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX + 1, ToY = FromY — 1, ToX <= MSize,

ToY > 0, getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX — 1, ToY = FromY + 1, ToX > 0, ToY <= MSize,

getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX — 1, ToY = FromY,

ToX > 0, getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

step (Labyrinth, MSize, FromX, FromY, ToX, ToY): ;

ToX = FromX — 1, ToY = FromY — 1, ToX > 0, ToY > 0, getelem (Labyrinth, ToX, ToY, Elem),

Elem = 0.

printline ([H], 1): ;

!,

write (H),

nl.

printline ([H | T], J): ;

NewJ = J — 1, write (H),

write (««),

printline (T, NewJ).

print ([H], 1, J): ;

!, printline (H, J).

print ([H | T], I, J): ;

NewI = I — 1, printline (H, J),

print (T, NewI, J).

operate (Cnt, PathMatrix, MSize, X, Y, I, J): ;

X = I,

Y = J,

markelem (Cnt, PathMatrix, X, Y, NewPathMatrix),

print (NewPathMatrix, MSize, MSize),

nl,

fail.

operate (Cnt, PathMatrix, MSize, X, Y, I, J): ;

markelem (Cnt, PathMatrix, X, Y, NewPathMatrix),

step (NewPathMatrix, MSize, X, Y, NewX, NewY),

NewCnt = Cnt + 1, operate (NewCnt, NewPathMatrix, MSize, NewX, NewY, I, J).

repeat.

repeat: ;

repeat.

case (Labyrinth, 1, MSize): ;

write («Enter starting point»), nl,

readint (X),

readint (Y),

write («Enter ending point»), nl,

readint (I),

readint (J),

openwrite (fop, «lab. txt»),

writedevice (fop),

operate (2, Labyrinth, MSize, X, Y, I, J).

case (_, 1, _): ;

file_str (fop, «lab. txt»),

closefile (fop),

fail.

case (_, 2, _): ;

!.

main: ;

write («Input the name of file: «), nl,

readln (Fname),

openread (fop, Fname),

readdevice (fop),

getmatrix (MSize, MatrixInFile),

closefile (fop),

reverselines (MSize, MatrixInFile, [], Labyrinth),

repeat,

write («Menu: «), nl,

write («1) Play labyrinth»), nl,

write («2) Exit»), nl,

readint (Choice), nl,

case (Labyrinth, Choice, MSize).

main.

GOAL

main.