Объединение, пересечение и разность множеств

Над множествами выполнимы объединение (+), пересечение (*) и разность (-).

Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.

var           chs1, chs2, chs3: set of char; begin           chs1:= ['a', 'b', 'd'];          chs2:= ['m', 'd', 'e'];          chs3:= chs1 + chs2 + ['k', 'n']; end.

Результат: chs3 = ['a', 'b', 'd', 'm', 'e', 'k', 'n'].

Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.

chs3:= chs1 * chs2;

Результат: chs3 = ['d'].

Разность двух множеств A и B (A – B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.

chs1:= ['a', 'e', 't'];chs2:= chs1 – ['e']                           { ['a', 't'] } chs3:= ['m', 'n', 't'] – chs2 { ['m', 'n'] }

Манипулируя операциями над множествами, можно добавлять элементы к множествам или удалять их.

Для вставки и удаления элементов при работе с множествами в Pascal введены две процедуры:

include (имя_множества, элемент)exclude (имя_множества, элемент)

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

include (chs1, 'g');    { аналогично chs 1 + [' g '] } exclude (chs2, 'a'); { аналогично chs2 - ['a'] }

Другие операции над множествами

Над множествами можно выполнять четыре операции сравнения: =, <>, >=, <=.

Два множества A и B равны (A = B), если каждый элемент множества A является элементом множества B и наоборот.

Два множества A и B не равны (A <> B), если они отличаются хотя бы одним элементом.

Множество A является подмножеством множества B (A <= B, или B >= A), если каждый элемент из A присутствует в B.

 

 

 

Имеется также возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in (операция вхождения). Пусть A – множество элементов некоторого базового типа, а x – переменная (константа, выражение) этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A.

Все операции сравнения множеств, а также операция in возвращают логическое значение true или false.

Например, 4 in [3, 4, 7, 9] –– true, 5 in [3, 4, 7, 9] –– false.

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

1) Натуральное число n является двухзначным. Вместо выражения (n >= 10) and (n <=99) можно записать n in [10..99].

2) Символ c является русской буквой. Вместо выражения (c >= ‘А’) and (c <= ‘Я’) or (c>=‘а’) and (c<=‘п’) or (c>=‘р’) and (c<=‘я’) пишем c in [‘А’.. ‘Я’, ‘а’.. ‘п’, ‘р’.. ‘я’] и т.д.

 

В сложных выражениях над множествами операции имеют следующие приоритеты:

1. *

2. +, -

3. =, <>, <=, >=, in

 

Рассмотрим несколько примеров.

Пример. Пусть в вашем распоряжении имеется множество из трех монет разного достоинства: 1 р, 5 р, 10 р. Из этих монет можно составить следующие подмножества (их число равно 2³ = 8):

1. {1};

2. {5};

3. {10};

4. {1, 5};

5. {1, 10};

6. {5, 10};

7. {1, 5, 10};

8. { }

Эти подмножества и будут принадлежать некоторому множеству, тип которого назовем sum. Сами элементы (монеты), из которых составляется подмножество, пусть принадлежат некоторому базовому типу, который назовем monet.
Опишем типы данных этого примера:

Type

monet = (m1, m5, m10);

sum = set of monet;

Пример. Рассмотрим в качестве элементов базового типа сигналы от 4-х абонентов (ab1, ab2, ab3, ab4), поступающие на телефонную станцию. Обозначим базовый тип через abonent:

type abonent = (ab1, ab2, ab3, ab4),

тогда комбинации сигналов можно описать переменной типа множество. Назовем этот тип sing:

sing = set of abonent;

Тип sing описывает 16 комбинаций.

В общем виде тип множество описывается так:

type a = set of tc;

здесь a – идентификатор типа (произвольный); tc – тип компонент множества называемый базовым типом.

 

Значение переменной типа множество изображается путем перечисления конкретных компонентов, разделенных запятыми и заключенных в квадратные скобки.

 

ПРИМЕР 1 program test; var S: set of char; c: char; begin s:= []; repeat read (c); include (s, c); until c = '.'; for c:= '0' to '9' do if c in s then writeLn (c) end.

Итак что же делает эта программа? Для начала пользователь вводит в цикле символы, пока не нажал точку. При этом мы заполняем множество S этими символами. После этого выводим на экран те символы, которые оказались цифрами. Для этого нам надо проверить вхождение цифр в это множество. Что мы благополучно и делаем. Ещё один пример использования множеств - стандартный запрос Y / N - раньше надо было писать 2 условия if (key = 'Y') or (key = 'y') теперь же всё гораздо проще - if key in ['Y', 'y'], так же можно добавть проверку, не нажал ли пользователь букву У вместо Y:) key in ['Y', 'y', 'У', 'у'] или же добавить ещё проверку на букву Д....

Пример 2. Дана символьная строка. Подсчитать в ней количество знаков препинания (. -,;:! *?).

Program P1;

Var S: String; I,K: Byte;

Begin

ReadLn(S); K:=0;

For I:=1 To Length(S) Do

If S[I] In ['.','-',',',';',':', '!', '*','?']

Then K:=K+1;

WriteLn('Число знаков препинания равно',К)

End.

В этом примере использована множественная константа с символьным типом элементов. Эту задачу можно решить и без множества, записав в операторе If длинное логическое выражение: (S[l]='.') Or (S[l]='-') и т.д. Использование множества сокращает запись.