Множества и их представление на языке Пролог. Простые программы обработки множеств
5.5.1 Основные определения.
Списки ¾ структуры данных, с помощью которых можно представлять множества и графы в программах на языке Пролог. Множества отличаются от списков тем, что в списках могут быть повторяющиеся элементы, а во множествах ¾ нет. С другой стороны, в списках порядок следования элементов имеет значения, а множества могут быть неупорядоченными. В следующих параграфах будут рассмотрены предикаты, выполняющие операции над множествами.
5.5.2 Предикат unionset.
Предикат unionset определяет операцию объединения двух множеств. Объединением двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат или множеству X, или множеству Y, или обоим множествам одновременно.
Предикат unionset(X,Y,Z) ¾истинен, если множество Z является объединением множеств X и Y. Схема отношения этого предиката имеет вид:
unionset(<список>,<список>,<список>).
Декларативное описание предиката unionset(X,Y,Z)формулируется следующим образом:
v Объединение пустого множества с непустым множеством Х есть множество Х.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура unionset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура unionset с аргументами Xs и Y. При этом терм H помещается в результирующий список.
|
|
|
Процедура unuonset(X,Y) состоит из трех правил:
unionset([],X,X).
unionset([H|Xs],Y,Z):-member(H,Y),!,unionset(Xs,Y,Z).
unionset([H|Xs],Y,[H|Z]):-unionset(Xs,Y,Z).
Процедура unionset выполняется следующим образом:
? ¾ unionset([a,b,c],[d,a,b,f],Z).
ТР: unionset([a,b,c],[d,a,b,f],Z).
Шаг 1: ТЦ: unionset([a,b,c], [d,a,b,f] ,Z).
Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)
Пр2: unionset([a|[b,c]],[d,a,b,f],Z):-member(a,[d,a,b,f]),!,unionset([b,c], [d,a,b,f],Z).
ТР: member(a,[d,a,b,f]),!,unionset([b,c],[d,a,b,f],Z).
Шаг 2: ТЦ: member(a,[d,a,b,f]) Þ успех[3]
ТР: unionset([b,c],[d,a,b,f],Z1).
Шаг 3: ТЦ: unionset([b,c],[d,a,b,f],Z).
Пр1: [b,c] =[] Þ неуспех (списки разной длины)
Пр2: unionset([b|[c]],[d,b,a,f],Z):-member(b,[d,a,b,f]),!,unionset([c],[d,a,b,f],Z).
ТР: member(b,[d,a,b,f]),!,unionset([c],[d,b,a,f],Z).
Шаг 4: ТЦ: member(b,[d,a,b,f]) Þ успех
ТР: unionset([c],[ d,a,b,f],Z).
Шаг 5: ТЦ: unionset([c],[ d,a,b,f ],Z).
Пр1: [c] =[] Þ неуспех (списки разной длины)
Пр2: unionset([c|[]],[d,a,b,f],Z):-member(c,[d,a,b,f]),!,unionset([],[d,a,b,f],Z).
ТР: member(c,[d,a,b,f]),!,unionset([],[d,a,b,f ],Z).
Шаг 6: ТЦ: member(с,[d,a,b,f]) Þ неуспех
Возврат.
Пр3: unionset([c|[]],[ d,a,b,f ],[c|Z1]):- unionset([],[d,a,b,f ],Z1).
Z=[c|Z1]
ТР: unionset([],[d,a,b,f ],Z1).
|
|
|
Шаг 7: ТЦ: unionset([],[d,a,b,f ] ,Z1).
Пр1: [] =[] Þ успех при подстановке Z1=[d,a,b,f ].
Выход из рекурсии на шаг 6, получается подстановка Z=[c|Z1] или Z=[c,d,a,b,f].
Выход из рекурсии на шаг 5, Z=[c,d,a,b,f].
Выход из рекурсии на шаг 3, Z=[c,d,a,b,f].
Выход из рекурсии на шаг 1, Z=[c,d,a,b,f].
ТР: ÿ ¾успех.
Результат вычисления запроса Z=[c,d,a,b,f].Þ успех.
5.5.3. Пересечение множеств.
Предикат interset определяет операцию пересечения двух множеств. Пересечением двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат и множеству X, и множеству Y одновременно.
Предикат interset (X,Y,Z) ¾истинен, если множество Z является пересечением множеств X и Y. Схема отношения этого предиката имеет вид:
interset(<список>,<список>,<список>).
Декларативное описание предиката interset(X,Y,Z)формулируется следующим образом:
v Пересечение пустого множества с непустым множеством Х есть пустое множество.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура interset с аргументами Xs и Y. При этом терм H помещается в результирующий список.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура interset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.
|
|
|
Процедура interset(X,Y,Z) состоит из трех правил:
interset([],X,[]).
interset([H|Xs],Y, [H|Z]):-member(H,Y),!,interset(Xs,Y,Z).
interset([H|Xs],Y,Z):-interset(Xs,Y,Z).
Процедура interset выполняется следующим образом:
? ¾ interset([a,b,c],[d,a,b,f],Z).
ТР: interset([a,b,c],[d,a,b,f],Z).
Шаг 1: ТЦ: interset([a,b,c], [d,a,b,f] ,Z).
Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)
Пр2: interset([a|[b,c]],[d,a,b,f],[a|Z1]):-member(a,[d,a,b,f]),!,interset([b,c], [d,a,b,f],Z1).
при этом Z=[a|Z1]
ТР: member(a,[d,a,b,f]),!,interset([b,c],[d,a,b,f],Z).
Шаг 2: ТЦ: member(a,[d,a,b,f]) Þ успех
ТР: interset([b,c],[d,a,b,f],Z1).
Шаг 3: ТЦ: interset([b,c],[d,a,b,f],Z1).
Пр1: [b,c] =[] Þ неуспех (списки разной длины)
Пр2: interset([b|[c]],[d,b,a,f],[b|Z2]):-member(b,[d,a,b,f]),!,interset([c],[d,a,b,f],Z2).
при этом Z1=[b|Z2]
ТР: member(b,[d,a,b,f]),!,interset([c],[d,b,a,f],Z2).
Шаг 4: ТЦ: member(b,[d,a,b,f]) Þ успех
ТР: interset([c],[ d,a,b,f],Z2).
Шаг 5: ТЦ: interset([c],[ d,a,b,f ],Z2).
Пр1: [c] =[] Þ неуспех (списки разной длины)
Пр2: interset([c|[]],[d,a,b,f],[c|Z3]):-member(c,[d,a,b,f]),!,interset([],[d,a,b,f],Z3).
ТР: member(c,[d,a,b,f]),!,interset([],[d,a,b,f ],Z3).
Шаг 6: ТЦ: member(с,[d,a,b,f]) Þ неуспех
|
|
|
Возврат.
Пр3: interset([c|[]],[ d,a,b,f ],Z2):- interset([],[d,a,b,f ],Z2).
ТР: interset([],[d,a,b,f ],Z2).
Шаг 7: ТЦ: interset([],[d,a,b,f ] ,Z2).
Пр1: [] =[] Þ успех при подстановке Z2=[].
Выход из рекурсии на шаг 3, Z1=[b|Z2] или Z1=[b].
Выход из рекурсии на шаг 1, Z=[a|Z1] или Z=[a|[b]] или Z=[a,b].
ТР: ÿ ¾успех.
Результат вычисления запроса Z=[a,b].Þ успех.
5.5.4. Разность множеств.
Предикат difset определяет операцию разности двух множеств. Разностью двух множеств X и Y является множество Z, состоящее из элементов, которые принадлежат множеству X, но не принадлежат множеству Y.
Предикат difset (X,Y,Z) ¾истинен, если множество Z является разностью множеств X и Y. Схема отношения этого предиката имеет вид:
difset(<список>,<список>,<список>).
Декларативное описание предиката difset(X,Y,Z)формулируется следующим образом:
v Разность пустого множества и непустого множеством Х есть пустое множество.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н не принадлежит второму списку Y, то рекурсивно вызывается процедура difset с аргументами Xs и Y. При этом терм H помещается в результирующий список.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Если голова первого списка Н принадлежит второму списку Y, то рекурсивно вызывается процедура difset с аргументами Xs и Y. При этом терм H в результирующий список не помещается.
Процедура difset(X,Y,Z) состоит из трех правил:
difset([],X,[]).
difset([H|Xs],Y, [H|Z]):-not(member(H,Y)),!,difset(Xs,Y,Z).
difset([H|Xs],Y,Z):-difset(Xs,Y,Z).
Процедура difset выполняется следующим образом:
? ¾ difset([a,b,c],[d,a,b,f],Z).
ТР: difset([a,b,c],[d,a,b,f],Z).
Шаг 1: ТЦ: difset([a,b,c], [d,a,b,f] ,Z).
Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)
Пр2: difset([a|[b,c]],[d,a,b,f],[a|Z1]):-not(member(a,[d,a,b,f])),!,difset([b,c], [d,a,b,f],Z1).
при этом Z=[a|Z1]
ТР: not(member(a,[d,a,b,f])),!,difset([b,c],[d,a,b,f],Z).
Шаг 2: ТЦ: not(member(a,[d,a,b,f])) Þнеуспех[4]
Возврат.
Пр3: difset([a|[b,c]],[d,a,b,f],Z):-difset([b,c], [d,a,b,f],Z).
ТР: difset([b,c],[d,a,b,f],Z).
Шаг 3: ТЦ: difset([b,c],[d,a,b,f],Z).
Пр1: [b,c] =[] Þ неуспех (списки разной длины)
Пр2: difset([b|[c]],[d,b,a,f],[b|Z1]):-not(member(b,[d,a,b,f])),!,difset([c],[d,a,b,f],Z1).
при этом Z=[b|Z1]
ТР: not(member(b,[d,a,b,f])),!,difset([c],[d,b,a,f],Z1).
Шаг 4: ТЦ: not(member(b,[d,a,b,f])) Þ неуспех
Возврат.
Пр3: difset([b|c]],[d,a,b,f],Z):-difset([c], [d,a,b,f],Z).
ТР: difset([c],[ d,a,b,f],Z).
Шаг 5: ТЦ: difset([c],[ d,a,b,f ],Z).
Пр1: [c] =[] Þ неуспех (списки разной длины)
Пр2: difset([c|[]],[d,a,b,f],[c|Z1]):-not(member(c,[d,a,b,f])),!,difset([],[d,a,b,f],Z1).
при этом Z=[c|Z1]
ТР: not(member(c,[d,a,b,f])),!,difset([],[d,a,b,f ],Z2).
Шаг 6: ТЦ: not(member(с,[d,a,b,f])) Þ успех
Шаг 7: ТЦ: difset([],[d,a,b,f ] ,Z1).
Пр1: [] =[] Þ успех при подстановке Z1=[].
Выход из рекурсии на шаг 5, Z=[c|Z2] или Z=[c].
Выход из рекурсии на шаг 3, Z=[c].
Выход из рекурсии на шаг 1, Z=[c].
ТР: ÿ ¾успех.
Результат вычисления запроса Z=[c].Þ успех.
5.5.5. Определение подмножества.
Предикат subset определяет, является ли множество подмножеством другого множества. Множество X является подмножеством множества Y, если все элементы X, принадлежат множеству Y.
Предикат subset(X,Y) ¾истинен, если множество X является подмножеством Y. Схема отношения этого предиката имеет вид:
subset(<список>,<список>).
Декларативное описание предиката subset(X,Y)формулируется следующим образом.
v Пустое множество является подмножеством любого множества.
v Список, определяющий первое множество Х можно разделить на голову Н и хвост Xs. Множество X есть подмножество Y, если голова первого списка Н принадлежит второму списку Y и Xs есть подмножество множества Y.
Процедура subset(X,Y) состоит из двух правил:
subset([],Y).
subset([H|Xs],Y):-member(H,Y),subset(Xs,Y).
Рассмотрим пример запроса к процедуре subset.
Процедура subset выполняется следующим образом:
? ¾ subset([a,b,c],[d,a,b,c,f]).
ТР: subset([a,b,c],[d,a,b,c,f]).
Шаг 1: ТЦ: subset([a,b,c], [d,a,b,c,f]).
Пр1: [a,b,c] =[] Þ неуспех (списки разной длины)
Пр2: subset([a|[b,c]],[d,a,b,c,f]):-member(a,[d,a,b,f])subset([b,c], [d,a,b,c,f]).
ТР: member(a,[d,a,b,c,f])),subset([b,c],[d,a,b,c,f]).
Шаг 2: ТЦ: member(a,[d,a,b,c,f]) Þуспех[5]
ТР: subset([b,c],[d,a,b,c,f]).
Шаг 3: ТЦ: subset([b,c],[d,a,b,c,f]).
Пр1: [b,c] =[] Þ неуспех (списки разной длины)
Пр2: subset([b|[c]],[d,a,b,c,f]):-member(b,[d,a,b,c,f]))subset([c],[d,a,b,c,f]).
ТР: member(b,[d,a,b,c,f])),subset([c],[d,b,a,c,f]).
Шаг 4: ТЦ: member(b,[d,a,b,c,f]) Þ успех
ТР: subset([c],[ d,a,b,f],Z).
Шаг 5: ТЦ: subset([c],[ d,a,b,c,f ]).
Пр1: [c] =[] Þ неуспех (списки разной длины)
Пр2: subset([c|[]],[d,a,b,f],[c|Z1]):-member(c,[d,a,b,c,f])),subset([],[d,a,b,c,f]).
ТР: member(c,[d,a,b,c,f])),subset([],[d,a,b,c,f ]).
Шаг 6: ТЦ: member(с,[d,a,b,f,c]) Þ успех
Шаг 7: ТЦ: subset([],[d,a,b,f ] ).
Пр1: [] =[] Þ успех.
Выход из рекурсии на шаг 5.
Выход из рекурсии на шаг 3.
Выход из рекурсии на шаг 1.
ТР: ÿ ¾успех.
Результат вычисления запроса Þ успех.
Дата добавления: 2018-04-04; просмотров: 1291; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!