Сортировка списков

Списки

Метод повтора

Метод отсечения и отката.

В основе этого метода лежит использование комбинации предикатов fail (для имитации неудачи и искусственной организации отката) и "!" (отсечение или cut), который позволяет прервать этот процесс в случае выполнения какого-то условия.

Пример:

PREDICATES

nal(symbol, symbol)

zar(symbol)

min(symbol)

max(symbol)

dop(symbol)

prof(symbol,symbol)

CLAUSES

nal(Pred, Vid_nal):-zar(Pred), prof(Pred, “Образование”),!, fail.

nal(Pred, Vid_nal):-zar(Pred), max(Vid_nal).

max(X):-min(X);dop(X).

min(“Местные”).

min(“На прибыль”).

dop(“На добавочную стоимость”).

zar(“РГРТУ”).

zar(“контора РиК”).

prof(“РГРТУ”, “Образование”).

prof(“Контора РиК”, “Комерция”).

Также использует откат, однако в отличие от отката после неудачи, в котором откат осуществляется только после специально созданной неудачи, в этом методе откат возможен всегда за счет использования специального предиката, обычно кодируемого в виде:

repeat.

repeat:–

repeat.

Этот предикат всегда успешен после выполнения первого предложения процедуры в стек точек возврата запоминается указатель поскольку имеется ещё один альтернативный вариант. В теле второго предложения опять вызывается предикат repeat. Предикат repeat не является встроенным предикатом, а его имя – зарезервированным словом. Вместо этого имени можно использовать любое другое. С помощью подобного предиката можно организовывать циклы.

DATABASE

counter(integer)

PREDICATES

repeat

count

GOAL

count.

CLAUSES

repeat.

repeat:-repeat.

count:-assert(counter(0)),fail.

count:-repeat,counter(X),Y=X+1,retract(counter(X)), asserta(counter(Y)),write(Y), nl, Y=5.

В императивных языках основной структурой данных являются массивы, а в прологе списки. Списком называется упорядоченная последовательность элементов произвольной длины. Список задается перечислением элементов через запятую в квадратных списках.

Рассмотрим пример:

[Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]

[]-пустой список

listI = integer* /* список, элементы которого —

целые числа */

listR = real* /* список, состоящий из вещественных

чисел */

listC = char* /* список символов */

lists = string* /* список, состоящий из строк */

listL = listI* /* список, элементами которого являются

списки целых чисел */

Дадим рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;
2. структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

Вертикальная черта позволяет разделить на хвост и голову. Если хвост не пуст, то также можно разбить для пустого списка. Чтобы организовать работу списка, достаточно задать правило порядка перехода от обработки всего непустого списка к обработке его хвоста.

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

length([], 0). /* в пустом списке элементов нет */

length([_|T], L):–

length(T, L_T), /* L_T — количество

элементов в хвосте */

L = L_T + 1. /* L — количество элементов

исходного списка */

Пример. Создадим предикат, позволяющий проверить принадлежность элемента списку. Предикат будет иметь два аргумента: первый — искомое значение, второй — список, в котором производится поиск.

member(X,[X|_]). /* X — первый элемент списка */

member(X,[_|T]):–

member(X,T). /* X принадлежит хвосту T*/

GOAL

member(2, [1, 2, 3]).

Результат:

X=1

X=2

X=3

Пример. Создадим предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат соединения.

conc([ ], L, L). /* при присоединении пустого списка

к списку L получим список L */

conc([H|T], L, [H|T1]):–

conc(T,L,T1). /* соединяем хвост и список L, получаем

хвост результата */

GOAL

сonc([1,2,3],[4,5],X)

Результат:

X= [1, 2, 3, 4, 5]

Пример. Разработаем предикат, позволяющий "обратить" список (записать его элементы в обратном порядке). Предикат будет иметь два аргумента: первый — исходный список, второй — список, получающийся в результате записи элементов первого аргумента в обратном порядке.

reverse([ ],[ ]). /* обращение пустого списка дает пустой

список*/

reverse([X|T],Z):–

reverse(T,S), conc(S,[X],Z).

/* обращаем хвост и приписываем к нему

справа первый элемент исходного

списка*/

Пример. Создадим предикат, который позволит проверить, является ли список палиндромом. Палиндромом называется список, который совпадает со своим обращением. Соответственно, у данного предиката будет всего один аргумент (список, который проверяем на "палиндромность").

palindrom(L):–

reverse (L,L).

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

n_element([X|_],1,X).

n_element([_|L],N,Y):–

N1=N–1,

n_element(L,N1,Y).

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

delete_all(_,[],[]).

delete_all(X,[X|L],L1):–

delete_all (X,L,L1).

delete_all (X,[Y|L],[Y|L1]):–

X<>Y,

delete_all (X,L,L1).

DOMAINS

listI = integer*

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

sum([], 0). /* сумма элементов пустого списка равна

нулю */

sum([H|T], S):–

sum(T, S_T), /* S_T — сумма элементов хвоста */

S = S_T + H. /* S — сумма элементов исходного

списка */

Пример. Напишем предикат, вычисляющий среднее арифметическое элементов списка.

avg(L,A):–

summa(L,S), /* помещаем в переменную S сумму

элементов списка */

length(L,K), /* переменная K равна количеству

элементов списка */

A=S/K. /* вычисляем среднее как отношение суммы

к количеству */

Пример. Создадим предикат, находящий минимальный элемент списка.

min_list([X],X). /* единственный элемент одноэлементного

списка является минимальным элементом

списка */

min_list([H|T],M):–

min_list(T,M_T), /* M_T — минимальный элемент хвоста */

min(H,M_T,M). /* M — минимум из M_T и первого элемента

исходного списка */

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

permutation([X,Y|T],[Y,X|T]):–

X>Y,!.

/* переставляем первые два

элемента, если первый больше

второго */

permutation([X|T],[X|T1]):–

permutation(T,T1).

/*переходим к перестановкам

в хвосте*/

bubble(L,L1):–

permutation(L,LL), /* вызываем предикат,

осуществляющий перестановку */

!,

bubble(LL,L1). /* пытаемся еще раз отсортировать

полученный список */

bubble(L,L). /* если перестановок не было, значит список

отсортирован */

Сортировка вставкой: основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте и весь список будет отсортирован.

ins_sort([ ],[ ]). /* отсортированный пустой список

остается пустым списком */

ins_sort([H|T],L):–

ins_sort(T,T_Sort),

/* T — хвост исходного списка,

T_Sort — отсортированный хвост

исходного списка */

insert(H,T_Sort,L).

/* вставляем H (первый элемент

исходного списка)в T_Sort,

получаем L (список, состоящий

из элементов исходного списка,

стоящих по неубыванию) */

insert(X,[],[X]). /* при вставке любого значения в пустой

список, получаем одноэлементный

список */

insert(X,[H|T],[H|T1]):–

X>H,!, /* если вставляемое значение

больше головы списка, значит

его нужно вставлять в хвост */

insert(X,T,T1).

/* вставляем X в хвост T,

в результате получаем

список T1 */

insert(X,T,[X|T]). /* это предложение (за счет отсечения

в предыдущем правиле) выполняется,

только если вставляемое значение

не больше головы списка T, значит,

добавляем его первым элементом

в список T */

Сортировка выбором: в списке находим минимальный элемент, используя предикат min_list, удаляем его из списка при помощи предиката delete_one.

delete_one(_,[],[]).

delete_one(X,[X|L],L):–!.

delete_one(X,[Y|L],[Y|L1]):–

delete_one(X,L,L1)

После удаления оставшийся список сортируем, и предписываем минимальный элемент в качестве головы к отсортированному списку.

choice([ ],[ ]). /* отсортированный пустой список

остается пустым списком */

choice(L,[X|T]):– /* приписываем X (минимальный элемент

списка L) к отсортированному

списку T */

min_list(L,X), /* X — минимальный элемент

списка L */

delete_one(X,L,L1),

/* L1 — результат удаления

первого вхождения

элемента X из списка L */

choice(L1,T). /* сортируем список L1,

результат обозначаем T */

Быстрая сортировка (Сортировка Хоара): выбирается некоторый барьерный элемент, относительно которого разбиваем исходный список на два подсписка. В первом элементы меньше барьерного, во второй большие или равные. Каждый из списков сортируем тем же способом. Затем приписываем к списку элементов меньше барьерного, сам барьерный элемент и список элементов не меньше барьерного. В итоге получаем список из элементов, стоящих в правильном порядке.

Вспомогательный предикат partition будет отвечать за разбиение списка на два подсписка. У него будет четыре аргумента. Первые два элемента — входные: первый — исходный список, второй — барьерный элемент. Третий и четвертый элементы — выходные, соответственно, список элементов исходного списка, которые меньше барьерного, и список, состоящий из элементов, которые не меньше барьерного элемента.

Предикат quick_sort будет реализовывать алгоритм быстрой сортировки Хоара. Он будет состоять из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого, после чего, используя предикат conc (созданный нами ранее), конкретизирует второй аргумент списком, получаемым объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка.

quick_sort([],[]). /* отсортированный пустой список

остается пустым списком */

quick_sort([H|T],O):–

partition(T,H,L,G),

/* делим список T на L (список

элементов меньших барьерного

элемента H) и G (список

элементов не меньших H) */

quick_sort(L,L_s),

/* список L_s — результат

упорядочивания элементов

списка L */

quick_sort(G,G_s),

/* аналогично, список G_s —

результат упорядочивания

элементов списка G */

conc(L_s,[H|G_s],O).

/* соединяем список L_s со

списком, у которого голова H,

а хвост G_s, результат

обозначаем O */

partition([],_,[],[]). /* как бы мы ни делили элементы

пустого списка, ничего кроме

пустых списков не получим */

partition([X|T],Y,[X|T1],Bs):–

X<Y,!,

partition(T,Y,T1,Bs).

/* если элемент X меньше барьерного

элемента Y, то мы добавляем его

в третий аргумент */

partition([X|T],Y,T1,[X|Bs]):–

partition(T,Y,T1,Bs).

/* в противном случае дописываем

его в четвертый аргумент */

Сортировка слияниями: разобьем список, который нужно упорядочить, на два подсписка. Упорядочим каждый из них тем же методом, после чего сольем упорядоченный подсписки обратно в один общий список. Этот метод придумал Фон Нейман в 1945 году. Потребуются вспомогательные предикаты.

Для начала создадим предикат, который будет делить исходный список на два. Он будет состоять из двух фактов и правила. Первый факт будет утверждать, что пустой список можно разбить только на два пустых подсписка. Второй факт будет предлагать разбиение одноэлементного списка на тот же одноэлементный список и пустой список. Правило будет работать в случаях, не охваченных фактами, т.е. когда упорядочиваемый список содержит не менее двух элементов. В этой ситуации мы будем отправлять первый элемент списка в первый подсписок, второй элемент — во второй подсписок, и продолжать распределять элементы хвоста исходного списка.

splitting([],[],[])./* пустой список можно расщепить

только на пустые подсписки */

splitting([H],[H],[]). /* одноэлементный список разбиваем

на одноэлементный список

и пустой список */

splitting([H1,H2|T],[H1|T1],[H2|T2]):–

splitting(T,T1,T2).

/* элемент H1 отправляем в первый

подсписок, элемент H2 — во второй

подсписок, хвост T разбиваем

на подсписки T1 и T2 */

Предикат, который будет непосредственно осуществлять сортировку списка. Он будет состоять из трех предложений. Первое будет декларировать очевидный факт, что при сортировке пустого списка получается пустой список. Второе утверждает, что одноэлементный список также уже является упорядоченным. В третьем правиле будет содержаться суть метода сортировки слиянием. Вначале список расщепляется на два подсписка с помощью предиката splitting, затем каждый из них сортируется рекурсивным вызовом предиката fusion_sort, и, наконец, используя предикат fusion, сливаем полученные упорядоченные подсписки в один список, который и будет результатом упорядочивания элементов исходного списка.

fusion_sort([],[]):–!./* отсортированный пустой список

остается пустым списком */

fusion_sort([H],[H]):–!. /* одноэлементный список

упорядочен */

fusion_sort(L,L_s):–

splitting(L,L1,L2),

/* расщепляем список L на два

подсписка */

fusion_sort(L1,L1_s),

/* L1_s — результат сортировки

L1 */

fusion_sort(L2,L2_s),

/* L2_s — результат сортировки

L2 */

fusion(L1_s,L2_s,L_s).

/* сливаем L1_s и L2_s

в список L_s */

Как проверить, отсортирован ли список?

sorted([ ]). /* пустой список отсортирован */

sorted([_])./* одноэлементный список упорядочен */

sorted([X,Y|T]):–

X<=Y,

sorted([Y|T]).

/* список упорядочен, если первые

два элемента расположены

в правильном порядке и список,

образованный вторым элементом

и хвостом исходного, упорядочен */

Дата добавления: 2014-01-07