Точно Не проект 2 / Не books / Источник_1
.pdfЯзык Пролог |
341 |
|
|
Вызов предиката name вернёт значение истина, если L – список ASCII-кодов символов, образующих атом А, например:
?– name (X, [97,105]). X = ai
?– name (ab,L).
L = [97,98]
Предикат functor(T,F,A) будет истинным, если главный функтор F имеет терм Т с арностью А, например:
? – functor(f(a, x), F, A). F = f, A = z
Вызов предиката arg(N,T,A) вернёт значение истина, если аргумент А
–N-ый аргумент терма Т, например:
?– arg(2, f(x, a (1), b), A). A = a(1)
Предикат T = ..L будет истинным, если L– список, первым элементом которого является главный функтор терма Т, за которым следуют аргументы терма Т, например:
?– f(a, b) = ..L. L = [f, a, b]
?– T = ..[быстро, автомобиль]. T = быстро(автомобиль).
Приведем более содержательные примеры использования рассмотренных предикатов при создании и декомпозиции термов.
Пример 1. Определим предикат ввод_атома, выполняющий чтение символов из входного потока и формирующий из них атом. При этом воспользуемся предикатом name. Определяемый предикат будет считывать символы входного потока, пока не встретится символ начала новой строки. Аргументом предиката ввод_атома(Х) является переменная, которая конкретизируется последовательностью символов, вводимых пользователем.
ввод_атома(Х):– |
% ввести символ |
get0(C), |
% если С- символ перехода |
(С=13; |
% на новую строку, то |
|
% закончить работу |
ввод_символов(С, Cписок)), |
% ввести символы в список |
name(X, Cписок)),!. |
% преобразовать список в атом |
Язык Пролог |
343 |
|
|
будет получен ответ
Y = [1, 4].
6.10.3.Предикаты работы с базой данных
ВПрологе имеется ряд встроенных предикатов, которые позволяют корректировать базу данных в процессе выполнения программ. К ним от-
носят следующие предикаты: assert(X), asserta(X), assertz(X), retract(X).
Предикат assert(X) добавляет в базу данных утверждение Х. Напри-
мер:
?– assert(столица(‘Украина’, ‘Киев’)). Yes
?– столица(‘Украина’, X).
X = Киев
Предикат asserta(X) добавляет утверждение Х в базу данных и помещает его перед другими утверждениями, соответствующими этому же факту или правилу. Предикат assertz(X) определяется аналогично asserta(X), но утверждения помещаются после других утверждений. Предикат retract(X) выполняет поиск утверждения Х в базе данных и удаляет первое найденное утверждение.
Совместное использование рассмотренных предикатов позволяет изменять базу данных. Определим простой предикат, для изменения значения факта, указывающего текущий день месяца:
день (9). изменить_день:-
день(Х), Y is X+1, retract(день (Х)), assert(день (Y).
При каждом вызове предиката изменить_день текущая дата будет увеличиваться на единицу:
?– изменить_день. Yes
?– день(Х).
Х= 10.
Если предикаты группы assert используются для добавления в базу данных правила, то добавляемое правило дополнительно заключается в скобки:
? – assert((a(X): – b(X), с(X))).
Язык Пролог |
345 |
|
|
6.11.Решение задач на языке Пролог
6.11.1.Создание и обработка бинарных деревьев
Одной из широко используемых структур данных, применяемых в программировании, являются бинарные деревья. Бинарное дерево – это структура данных, состоящая из левого бинарного поддерева, корня и правого бинарного поддерева. Элементы, расположенные в вершинах бинарного дерева, упорядочены в соответствии с некоторым признаком. При этом любой элемент левого поддерева всегда меньше корневого элемента, а любой элемент правого поддерева всегда больше корня. На рисунке 6.9 изображено бинарное дерево, вершины которого представлены буквами. Дерево упорядочено в соответствии с алфавитом.
Будем представлять бинарное дерево термом вида дерево(Лд,К,Пд), где Лд – левое поддерево, К – корень, а Пд – правое поддерево. Пустое бинарное дерево будем обозначать атомом nil. Тогда бинарное дерево, изображенное на рисунке 6.9, можно описать следующим образом:
дерево(дерево(дерево(nil, a, nil), д, дерево(nil, e, nil)), ж, дерево(nil, к, nil))
Рисунок 6.9 – Бинарное дерево
Применение бинарных деревьев существенно повышает эффективность поиска элементов данных по сравнению со списками.
Определим отношение принадлежит(Х,Д), которое позволяет установить, входит ли элемент Х в бинарное дерево Д. Определение отношения будет основано на следующих правилах:
а) если Х совпадает с корнем дерева Д, то Х входит в дерево; б) если Х меньше, чем корень дерева Д, то выполнить поиск Х в левом
поддереве; в) если Х больше, чем корень дерева Д, то выполнить поиск Х в пра-
вом поддереве.
Запишем соответствующие утверждения на Прологе:
принадлежит(Х, дерево(Лд, Х, Пд)). |
% определение а) |
Язык Пролог |
347 |
|
|
Отношение добавить(Д, Х, Д1) можно использовать для преобразования списка в бинарное дерево:
список_в_дерево([ ], nil). список_в_дерево([H|T], Д1): –
список_в_дерево(Т, Д), добавить(Д, Н, Д1).
Рассмотренное отношение не гарантирует построения сбалансированного дерева. При его использовании необходимо следить за тем, чтобы список был неупорядоченным, иначе построенное дерево может оказаться вырожденным. Отношения, обеспечивающие построение приближенно сбалансированных деревьев, рассматриваются в [7].
Иногда требуется выполнить преобразование дерева в список. В этом случае можно воспользоваться определением:
дерево_в_список(nil, [ ]). дерево_в_список(дерево(Лд, К, Пд), С): –
дерево_в_список(Лд, С1), дерево_в_список(Пд, С2),
слияние(С1, [К|C2], C).
Здесь предикат слияние(С1,С2,С3) выполняет слияние списков С1, С2 и формирует список С3. Данный предикат соответствует предикату append, рассмотренному в §4.1.8.
Помимо поиска и добавления, при работе с бинарными деревьями необходимо уметь удалять вершины из бинарного дерева. Если требуется удалить вершину на уровне листа бинарного дерева, то для этого можно воспользоваться отношением добавить:
удалить_лист(Д1,Х,Д): – добавить(Д, Х, Д1).
Иными словами, удаление листа Х из дерева Д1 равносильно поиску такого дерева Д, добавление к которому элемента Х дает дерево Д1.
Если же требуется выполнить удаление элемента на уровне корня дерева, то задача становится сложнее. Основная проблема заключается в том, что удаление корневой вершины приводит к образованию “дыры”. В этом случае левое и правое поддеревья, находящиеся ниже удаленного элемента, могут быть потеряны. Чтобы избежать этого, образовавшуюся дыру необходимо заполнить, сохранив упорядоченность дерева. “Дыру” заполняют либо самым “левым” элементом из правого поддерева, либо самым “правым” элементом из левого поддерева. Ниже приведена программа, реализующая указанные требования:
удалить(дерево(nil, X, Пд), Х, Пд). |
% Лд отсутствует |
Язык Пролог |
349 |
|
|
b:– a. % "b" достижимо, если достигнуто "a"
c:– a. % "c" достижимо, если достигнуто "а"
d:– b.
. . . |
|
g1: – e. |
% "g1" достижимо, если достигнуто "е" |
а. |
% начальное состояние |
Для того чтобы узнать, имеет ли рассматриваемая задача решение, необходимо просто задать вопрос:
? – g1.
Получив такой вопрос, пролог-система выполнит поиск в глубину на графе, изображенном на рисунке 6.10. При этом поиск будет выполняться обратным методом – от цели к известным фактам. После обхода всех необходимых вершин графа, будет сформирован ответ “да”.
Для того чтобы осуществить прямой поиск (от фактов к цели), необходимо описать граф состояния (рисунок 6.10) в виде следующего набора правил:
а: – b. b: – d. b: – e.
. . .
e: – g1.
g1. % цель
Вэтом случае процесс поиска решения инициируется вопросом:
?– а.
Преимущество рассмотренного способа программирования поиска в глубину заключается в его простоте. К недостаткам следует отнести следующее:
–программа формирует ответ “да” или “нет”, но не возвращает при этом решающий путь, соответствующий ходу решения;
–если на графе состояний имеются циклы, то прологсистема может
войти в бесконечный цикл, обусловленный косвенными рекурсивными вызовами.
Чтобы исключить указанные недостатки изменим представление графа состояний. Опишем его не с помощью правил, а с помощью фактов вида:
после(X, Y).
Такой факт означает, что состояние задачи Y непосредственно следует из состояния Х. Тогда граф состояний, изображенный на рисунке 6.10, можно представить следующим набором фактов: