Лекции в ворде (1156536), страница 16
Текст из файла (страница 16)
собака (голди).
собака (фидо).
собака(реке).
то на запрос
?- bagof(D, co6aкa(D), L),
будет получен ответ
L=[реке, голди, фидо, рекс]
в то время как
?-setof(D, co6aкa(D), L). дает значение
L=[фидо, голди, рекc]
Пример: сложение многочленов
Теперь мы достаточно подготовлены к тому, чтобы использовать списки для решения задач. Вопрос, которым мы займемся, - представление и сложение многочленов.
Представление многочленов. Посмотрим, как можно представить многочлен вида
Р(х)=3+3х-4х^3+2х^9
Q(х)=4х+х^2-3х^3+7х^4+8х^5
Заметим, что каждое подвыражение (такое, как Зх ^3, Зх, 3) имеет самое большее две переменные компоненты: число, стоящее перед х, называемое коэффициентом, и число, стоящее после ^ - степень. Следовательно, подвыражение представляется термом
х(Коэффициент, Степень)
Так, 5х^2 записывается как х(5,2), х^З представляется как х(1,3), а поскольку х^0 равно 1, подвыражению 5 соответствует терм х(5,0).
Теперь запишем многочлен в виде списка. Приведенный выше многочлен Р(х), например, будет выглядеть следующим образом:
[x(3, 0), '+', x(3, l), '-', x(4, 3), '+', x(2, 9)]
Воспользуемся тем, что многочлен
3 + 3х - 4х^3 + 2х^9
допускает замену на эквивалентный
3 + 3х + (-4)х^3 + 2х^9 Тогда он выражается списком:
[х(3, 0), '+', х(3, 1), '+', х(-4, 3), '+', х(2, 9)]
В такой записи между термами всегда стоят знаки '+'. Следовательно, их можно опустить, и многочлен принимает окончательный вид:
[х(3, 0), х(3, 1), х(-4, 3), х(2, 9)]
Подразумевается, что между всеми термами списка стоят знаки '+'. Представлением многочлена Q(x) будет
[х(4, 1), х(1, 2), х(-3, 3), х(7, 4), х(8, 5)]
Сложение многочленов. Теперь напишем целевые утверждения для сложения двух многочленов. Сложение многочленов
3-2х^2+4х^3+6х^6
-1+3х^2-4х^3
в результате дает
2+х^2+6х^6
Аргументами целевого утверждения являются многочлены, представленные в виде списков. Ответ будет получен также в виде списка.
Сложение многочлена Р с многочленом Q осуществляется следующим образом:
Граничное условие:
Р, складываемый с [], дает Р.
[], складываемый с Q, дает Q.
Рекурсивное условие:
При сложении Р с Q, в результате чего получается многочлен R, возможны 4 случая:
а) степень первого терма в Р меньше, чем степень первого терма в Q. В этом случае первый терм многочлена Р образует первый терм в R, а хвост R получается при прибавлении хвоста Р к Q. Например, если Р и Q имеют вид
Р(х)=3х^2+5х^3
Q(x)=4x^3+3x^4
то первый терм R(x) равен 3х^2 (первому терму в Р(х)). Хвост R(x) равен 9х^3+3х^4, т.е. результату сложения Q(x) и хвоста Р(х);
б) степень первого терма в Р больше степени первого терма в Q. В данном случае первый терм в Q образует первый терм в R, а хвост R получается при прибавлении Р к хвосту Q. Например, если
Р(х)=2х^3+5х^'4
Q(x)=3x^3-x^4
то первый терм R(x) равен 3х^2 (первому терму в Q(x)), а хвост R(x) равен 2х^3+4х^4 (результату сложения Р(х) и хвоста Q(x));
в) степени первых термов в Р и Q равны, а сумма их коэффициентов отлична от нуля. В таком случае первый терм в R имеет коэффициент, равный сумме коэффициентов первых термов в Р и Q. Степень первого терма в R равна степени первого терма в Р (или Q). Хвост R получается при сложении хвоста Р и хвоста Q. Например, если Р и Q имеют вид
Р(х)=2х+3х^3
Q(x)=3x+4x^4
то первый терм многочлена R (х) равен 5х (результату сложения первого терма в Р(х) с первым термом в Q(x)). Хвост R(x) равен 3х^3+4х^4 (результату сложения хвоста Р(х) и хвоста Q(x));
г) степени первых термов в Р и Q одинаковы, но сумма коэффициентов равна нулю. В данном случае многочлен R равен результату сложения хвоста Р с хвостом Q. Например, если
р(х)=2+2х
Q(x)=2-3x^2
то
R(x)=2x-3x^2
(это результат сложения хвостов многочленов Р (х) и Q (х)).
Рассмотренный процесс сложения многочленов можно непосредственно записать на языке Пролог:
/* Граничные условия
слож_мн([], Q Q).
слож_мн(P, [], P).
/* Рекурсивное условие
/* (a)
слож_мн([x(Pc, Pp)|Pt], [x(Qc, Qp)|Qt],
[x(Pc,Pp)IRt]) :-
PpQp,
слож_мн(Рt, [х(Qс,Qр) | Qt], Rt).
/*(б)
слож_мн([x(Pc, Pp) | Pt], [x(Qc, Qp) | Qt],
[x(Qc, Qp) | Rt]) :-
PpQp,
слож_мн([x(Pc, Pp) | Pt], Qt, Rt).
/*(в)
слож_мн([x(Pc, Pp) | Pt], [х(Qc,Pp) | Qt],
[x(Rc, Pp) | Rt]) :-
Rc is Pc+Qc,
Rc =\= 0,
слож_мн(Pt, Qt,Rt).
/*(r)
слож_мн([х(Рс, Рр) | Pt],
[x(Qc.Pp) | Qt], Rt) :-
Re is Pc+Qc,
Rc =:= 0,
слож_мн(Pt, Qt, Rt).
Заметим, что в двух последних утверждениях проверка на равенство осуществляется следующим образом: степени первых термов складываемых утверждений обозначает одна и та же переменная Pp.
Списки как термы. В начале главы мы упомянули о том, что список представляется с помощью терма. Такой терм имеет функтор '.', Два аргумента и определяется рекурсивно. Первый аргумент является головой списка, а второй - термом, обозначающим хвост списка. Пустой список обозначается []. Тогда список [а, b] эквивалентен терму.(а,.(b, [])).
Таким образом, из списков, как и из термов, можно создавать вложенные структуры. Поэтому выражение
[[a, b], [c, d], [a], a]
есть правильно записанный список, и на запрос
?- [Н | Т]=[[а, b], с].
Пролог дает ответ
Н=[а, b]
Т=[с]
Бинарные деревья
ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ
Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья сами являются бинарными деревьями. На Рис. 14 показан пример бинарного дерева.
Рис. 14. Бинарное дерево.
Такие деревья можно представить термами вида
бд(Лд, К, Пд),
где Лд - левое поддерево, К - корень, а Пд - правое поддерево. Дл» обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.5.2.1 имеет левое поддерево
бд(бд(nil, d, nil), b, бд(nil, е, nil))
правое поддерево
бд(nil,с, nil)
и записывается целиком как
бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).
ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ
Описание множеств в виде списков позволяет использовать для множеств целевое утверждение принадлежит, определенное ранее для списков.
Однако для множеств, состоящих из большого числа элементов, списковые целевые утверждения становятся неэффективными. Рассмотрим, например, как целевое утверждение принадлежит (см. предыдущий разд.) позволяет моделировать принадлежность множеству. Пусть L - список, описывающий множество из первых 1024 натуральных чисел. Тогда при ответе на запрос
?- принадлежит(3000, b).
Прологу придется проверить все 1024 числа, прежде чем заключить, что такого числа нет:
нет
Представление множества бинарным деревом позволяет добиться лучшего результата. При этом бинарное дерево должно быть упорядочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве — больше. Поскольку мы определили поддерево как бинарное дерево, такое упорядочение применяется по всем поддеревьям. На Рис. 15 приведен пример упорядоченного бинарного дерева.
Дерево на Рис. 14 является неупорядоченным.
Рис. 15. Упорядоченное бинарное дерево.
Обратите внимание, что упорядочение приводит не к единственному варианту представления множества с помощью дерева. Например, на Рис. 16 изображено то же множество, что и на Рис. 15.
Будем называть линейным представление такого вида, как на Рис. 16, и сбалансированным - такое, как на Рис. 15.
Рис. 16. Линейное представление.
Моделирование принадлежности множеству. Имея множество, описанное бинарным деревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @<, выражающий отношение «меньше, чем», и оператор @>, выражающий отношение «больше, чем».
/* Граничное условие: Х принадлежит
/* дереву, если Х является корнем.
принадлежит_дереву(Х, бд(Лд, Х, Пд)),
/* Рекурсивные условия
/* Х принадлежит дереву, если Х больше
/* значении корня и находится в правом
/* поддереве:
принадлсжит_дереву(Х, бд(Лд, У, Пд)) :- X@Y,
припадлежит_дереву(Х, Пд).
/* Х принадлежит дереву, если Х меньше
/* значения корня и находится в левом
/* поддереве:
принадлежит_дереву(Х, бд(Лд ,У ,Пд)) :-X@Y,
принадлежит_дереву(Х, Лд).
Если множество из первых 1024 чисел описать с помощью сбалансированного бинарного дерева Т, то при ответе на запрос
?- принадлежит_дереву(3000, Т).
Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем ответит:
нет
Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.
Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядоченному бинарному дереву формулируется следующим образом:
Граничное условие:
Добавление Х к nil дает бд(nil, Х, nil).
Рекурсивные условия:
При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверенным, что результирующее дерево будет упорядоченным.
1. Х меньше,чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое поддерево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.
2. Х больше, чем К. В таком случае нужно добавить Х к Пд, чтобы получить правое поддерево. Левое поддерево равно Лд, а значение корня - К.
Такой формулировке задачи соответствует программа:
/* Граничное условие:
включ_бд(nil, Х, бд(nil, Х, nil)).
/* Рекурсивные условия:
/*(1)
включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :-
Х@К,
включ_бд(Лд,Х,Лднов).
/*(2)
включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :-
Х@К,
включ_бд(Пд, Х, Пднов).
На запрос
?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2).
будут получены значения
Т1=бд(nil, d, nil)
Т2=бд(бд(nil, а, nil), d, nil)
Процедуру включ_бд() можно использовать для построения упорядоченного дерева из списка:
/* Граничное условие:
список_в_дерево([], nil).
/* Рекурсивное условие:
список_в_дерево([Н | Т], Бд) :-
список_в_дерево(Т, Бд2),
включ_бд(Н, Бд2, Бд).
Заметим, что включ_бд не обеспечивает построения сбалансированного дерева. Однако существуют алгоритмы, гарантирующие такое построение.
Механизм возврата и процедурная семантика
При согласовании целевого утверждения в Прологе используется метод, известный под названием механизма возврата. В этой главе мы показываем, в каких случаях применяется механизм возврата, как он работает и как им пользоваться. Описывается декларативная и процедурная семантика процедур Пролога. Завершается глава обсуждением вопросов эффективности.
Механизм возврата
При попытке согласования целевого утверждения Пролог выбирает первое из тех утверждений, голова которых сопоставима с целевым утверждением. Если удастся согласовать тело утверждения, то целевое утверждение согласовано. Если нет, то Пролог переходит к следующему утверждению, голова которого сопоставима с целевым утверждением, и так далее до тех пор, пока целевое утверждение не будет согласовано или не будет доказано, что оно не согласуется с базой данных.
В качестве примера рассмотрим утверждения:
меньше(X.Y) :-
XY, write(X),
write ('меньше, чем'),write(Y).
меньше(Х.У) :-
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
