Декартово произведение множеств

⇐ ПредыдущаяСтр 12 из 17Следующая ⇒

Предикат dek определяет операцию декартова произведения двух множеств. Декартовым произведением двух множеств X={x_i} и Y={y_i} является множество Z, состоящее из пар элементов [x_i, y_i], где x_i принадлежат множеству X, а y_i принадлежат множеству Y.

Предикат dek(X,Y,Z) ¾истинен, если множество Z является декартовым произведением множеств X и Y. Схема отношения того предиката имеет вид:

dek(<список>,<список>,<список>).

В процедуре dek используются дополнительные предикаты pro и
append[6]. Предикат pro(X,Y,Z)¾истинен, если X есть терм, Y={Y_i}¾множество термов, а Z является множество пар вида [X, Y_i], где X есть заданный терм, а Y_i¾ соответствующий элемент множества Y. Схема отношения предиката pro имеет вид:

pro(<терм>,<список>,<список>).

Декларативное определение предиката pro(X,Y,Z) формулируется следующим образом.

v Список Y состоит из одного элемента. Тогда список Z является списком пар вида [X, Y_i].

v Список, определяющий множество Y можно разделить на голову Н и хвост T. Тогда список Z=[[X,H]|T1], если список список T1 есть результат процедуры pro(X,T,T1].

Декларативное описание предиката dek(X,Y,Z) формулируется следующим образом:

v Список X состоит из одного элемента. Тогда список Z является результатом процедуры pro(X,Y,Z1.

v Список, определяющий первое множество Х можно разделить на голову X и хвост T1. Если pro(X,Y,T2) и dek(T1,Y,T3) и append(T2,T3,Z) истинны, то Z есть декартово произведение списков X и Y.

Процедура pro(X,Y,Z) состоит из двух правил:

pro(X,[Y],[[X,Y]|[]]).
pro(X,[H|T], [[X,H]|T1]):-pro(X,T,T1).

Процедура dek(X,Y,Z) состоит из двух правил:

dek([X|[]],Y,Z):pro(X,Y,Z).
dek([X|T1],Y,Z):-pro(X,Y,T2), dek(T1,Y,T3),

append(T2,T3,Z).

Пример запроса к процедуре pro.

? ¾ pro(4,[1,2,3],Z).

Z=[4,2],[4,3],[4,3]]

Yes

Пример запроса к процедуре dek.

? ¾ dek([4,2][3,5,8],Z).

Z=[[4,3],[4,5],[4,8], [2,3],[2,5],[2,8]]

Yes

5.6 Пролог¾программы сортировки списков.

5.6.1. Метод прямого выбора.

Наиболее распространены три метода сортировки списков:

1. метод сортировки путем прямого выбора;

2. метод сортировки путем вставки;

3. метод сортировки с использованием перестановок элементов.

Алгоритм сортировки списка путем прямого выбора включает в себя следующие шаги:

1. В исходном списке S1 находится минимальный элемент Min и помещается в результирующий список S2.

2. Этот элемент удаляется из списка S1, и процедура поиска повторяется. С каждым шагом список S1 уменьшается.

3. Когда список S1 станет пустым, список S2 станет результирующим, упорядоченным по возрастанию списком.

Процедура sort_vibor использует следующие процедуры:

1. sort1(<исходный список>, <накапливающийся список>,
<результирующий список>) ¾ процедура накопления списка;

2. delete(<терм>, <список>, <список > ) ¾ процедура удаления элемента из списка;

3. append(<список>, <список>, <список > ) ¾ процедура объединения списков;

4. minlist(<список>, <терм> ) ¾ процедура определения минимального элемента в списке;

5. min(<терм>, <терм>, <терм> ) ¾ процедура определения меньшего из двух термов.

В 5-й процедуре сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_vibor(L1,LS)истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом прямого выбора. Списки L1 и LS являются списками числовых термов.

Процедура sort_vibor(L1,LS)состоит из следующих правил:

sort_vibor(L1,LS):¾sort1(L1,[],LS).

sort1(L1,L2,LS):¾minlist(L1,Min),append(L2,[Min],L3),
delete(Min,L1,LL),sort1(LL,L3,LS).

sort1([],LS,LS).

delete(A,[A|B],B).

append([],|L,L).

append([X|L1],L2,[X|L3) :¾ append(L1,L2,L3).

minlist([X],X).

minlist([X,Y|T],M) :¾ minlist([Y|T],MinN),min(X,MinN,M).

min(X,Y,X) :¾X=<Y.

min(X,Y,Y) :¾X>Y.

5.6.2. Метод вставки.

Алгоритм сортировки списка путем вставки заключается в следующем: для того, чтобы упорядочить непустой список L = [X|T], необходимо:

1) упорядочить хвост списка, получив список OT;

2) вставить голову X списка L в упорядоченный список OT, поместив X в такое место списка OT, что список OT остался бы упорядоченным.

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

Предикат insert(X,L1,L2) ¾истинен, если список L2 получается из упорядоченного списка L1 путем вставки терма X без нарушения порядка. Схема отношения этого предиката имеет вид:

insert(<терм>, <список>, <список>).

В процедуре insert сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_insert(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом вставки. Списки L1 и LS являются списками числовых термов.

Процедура sort_insert(L1,LS) состоит из следующих правил:

sort_insert([],[]).

sort_insert([X|T],OL):¾sort_insert(T,OT),insert(X,OT,OL).

insert(X,[],[X]).

insert(X,[Y|T],[X,Y|T]):¾ X=<Y.

insert(X,[Y|T],[Y|T1]):¾ X>Y,insert(X,T,T1).

Метод перестановок.

Алгоритм сортировки списка путем перестановки элементов заключается в следующем: для того, чтобы упорядочить непустой список L = [X|T], необходимо:

1. найти в списке L два смежных элемента X и Y, таких что X>Y,и поменять X и Y местами, получив таким образом новый список L1, затем рекурсивно применить эту процедуру к списку L1;

2. если в списке L нет ни одной пары смежных элементов X и Y, таких что X>Y, то список L упорядочен.

Процедура sort_p использует процедуру perest, которая переставляет два смежных элемента в порядке возрастания (или убывания).

Предикат perest(L1,L2) ¾истинен, если список L2 получается из упорядоченного списка L1 путем перестановки. Схема отношения этого предиката имеет вид:

perest(<список>, <список>).

В процедуре perest сравниваются числовые термы с помощью операций сравнения чисел >, <, >=, =< или символьные термы с помощью операций сравнения символов (@>, @<, @>=,@=<.

Предикат sort_p(L1,LS) истинен, если список LS получен из списка L1 путем упорядочения списка L1 по возрастанию методом перестановки элементов. Списки L1 и LS являются списками числовых термов.

Процедура sort_p(L1,LS) состоит из следующих правил:

sort_p(L,OL): ¾ perest(L,L1),!,sort_p(L1,OL).

sort_p(OL,OL).

perest([X,Y|T],[Y,X|T]): ¾X>Y.

perest([Z|T],[Z|T1]):¾ perest(T,T1).

Дата добавления: 2018-04-04; просмотров: 530; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 7 8 9 10 111213 14 15 16 Следующая ⇒

Мы поможем в написании ваших работ!