Программирование на языке пролог

Клоксин У.

Объединением множеств Xи Yявляется множество, содержащее все элементы, принадлежащие Xили Yили одновременно им обоим.

Пример: {a,b,c} {с,d,е} = {a,b,c,d,e}.

Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция 'принадлежность' реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежитв граничном случае нет символа

«отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:

принадлежит(Х,[Х|_]).

принадлежит(Х,[_|Y]):- принадлежит(Х,Y).

Следующая операция 'включение' реализуется предикатом включает, причем включает(Х, Y)завершается успешно, если Xявляется подмножеством Y, т. е. Yвключает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:

включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).

включает([],Y).

Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением Xи Yявляется Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:

пересечение([], X, []).

пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y),!,пересечение(R, Y,Z).

пересечение([Х|R],Y,Z):- пересечение(R, Y,Z).

Наконец, объединение. Целевое утверждение объединение (X,Y,Z)доказуемо, если объединением Xи Yявляется Z. Заметим, что реализация предиката объединениесконструирована на основе определений предикатов пересечениеи присоединить:

объединение([],Х,Х).

объединение([Х|R],Y,Z):- принадлежит(Х,Y),!,

объединение(R,Y,Z). объединение([X |R],Y,[X|Z]):- объединение(R,Y,Z).

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

7.7. Сортировка

Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат '‹'. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату '‹'. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше,о чем уже говорилось в гл. 3. Список [alpha,beta,gamma]упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.

Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние

элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньшеили любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y)доказуемо, если объекты Xи Yудовлетворяют требуемому порядку следования, т. е. если Xв некотором смысле меньше чем Y.

Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:

наивсорт(L1,L2):- перестановка(L1,L2),отсортировано(L2),!.

перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).

перестановка([],[]).

отсортировано(L):- отсортировано(0,L).

отсортировано(_,[]).

отсортировано(N,[H|T]):- упорядочено(N,Н),отсортировано(Н,T).

Используемый здесь предикат присоединитьмногократна определялся ранее. В этой программе предикаты имеют следующий смысл:

Наивсорт(L1, L2)означает, что L2– это список, являющийся упорядоченной версией списка L1;

Перестановка(L1, L2)означает, что L2– это список, содержащий все элементы списка L1в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.

Предикат отсортировано(L)означает, что числа в списке Lупорядочены в порядке возрастания; это – 'контролер'.

Процесс поиска упорядоченной версии списка заключается в создании некоторой перестановки элементов и проверки ее упорядоченности. Если это так, то единственный ответ найден. Иначе мы вынуждены продолжать создание перестановок. Это не очень эффективный метод сортировки списка.

При сортировке включениемкаждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение вклюсорт(X, Y)доказуемо тогда, когда список Yявляется упорядоченной версией списка X. Каждый элемент удаляется из головы списка и передается предикату вклюсорт2, который включает этот элемент в список и возвращает измененный список.

вклюсорт([],[]).

вклюсорт([Х|L],М):- вклюсорт(L,N), вклюсорт2(Х,N,М).

вклюсорт2(Х,[А|L],[А|М]):- упорядочено(А,Х),!,вклюсорт2(Х,L,М).

вклюсорт2(Х,L,[Х |L]).

Чтобы сделать предикат сортировки включением более универсальным, удобно задавать предикат проверки порядка следования в качестве аргумента предиката вклюсорт.Используем для этого предикат ' =..', который рассматривался в гл. 6:

вклюсорт([],[],_).