У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ Страница 42

Пример: {x,r,u}⊂{p,q,r,f,t,u,v,w,x,y,z}.

Пересечение: X∩Y

Пересечением множеств X и Y является множество, содержащее те элементы, которые одновременно принадлежат X и Y.

Пример: {r,a,p,i,d} ∩ {p,i,c,t,u,r,e} = {r,i,p}.

Объединение: X ∪ Y

Объединением множеств 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:

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

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

вклюсорт2(Х,[А|L],[А|М],0):-Р=..[O,А,Х], call(P),!, вклюсорт2(Х,L,М,O).

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

Теперь мы можем использовать такие цели как вклюсорт(А,В,'‹') и вклюсорт(А,В,меньше), т. е. отпадает необходимость в предикате упорядочено. Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.

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

пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).

пусорт(L,L).

присоединить([],L,L).

присоединить([Н|Т],L[Н|V]):- присоединить(Т,L,V).

Заметим, что здесь применяется тот же самый предикат присоединить, с которым мы встречались ранее. Этот пример отличается от предыдущих необходимостью возвратного хода после каждого найденного решения. Поэтому в первом правиле в определении пусорт «отсечение» не используется. Эта программа еще один пример «недетерминированного» программирования,- для выбора элементов списка L здесь используется предикат присоединить. При этом контроль полноты выполненных перестановок целиком возложен на присоединить.