Множества

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

Понятие множества является одним из основных понятий современной математики.

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

Под множеством в Паскале понимается неупорядоченный набор фиксированного количества (не более 255) неповторяющихся однотипных элементов, имеющих общее имя – имя множества.

В отличие от массива – упорядоченной совокупности элементов, в которой каждый элемент однозначно определяется значением своего индекса (индексов), элементы множества таких индексов не имеют. Они размещаются во множестве неупорядоченно, поэтому значение отдельного элемента нельзя прочитать из множества, а можно только установить, входит или нет он в данное множество. Значит, множества используются в тех случаях, когда интерес представляет не конкретное значение отдельного элемента множества, а лишь факт его наличия или отсутствия в данном множестве однотипных элементов.

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

1. целого (множество целых чисел, не более 255 чисел),

2. логического (множество, состоящее из двух логических констант: TRUE и FALSE),

3. символьного (множество символов таблицы ASCII),

4. перечисляемого,

5. интервального.

Таким образом, в Паскале не определено множество, состоящее из чисел с дробной частью (REAL).

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

1. объявлением его имени и типа в разделе описания переменных Var :

Var r : Set Of ‘a ’. . ’c’;

d : Set Of 1 . . 4;

Описано множество r символов алфавита от ‘a’ до ‘c’ и множество d целых чисел 1, 2, 3, 4.

Внимание! Между начальным и конечным значениями интервала ставятся две точки!

2. объявлением типа множества в разделе определения типов Type и его имени – в разделе описания переменных Var :

Type TSymb = Set Of ‘a’ . . ‘c’;

TNumb = Set Of 1 . . 4;

Var r : TSymb;

d : TNumb;

3. заданием множества как типизированной константы:

Constr : Set Of ‘a ’. . ’c’ = [‘a’,’c’];

d : Set Of 1 . . 4 = [2,1,3];

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

Элементы ножества можно задавать следующими способами:

a)перечислением отдельных его значений:

[‘c’, ‘a’, ‘e’] [76, 102, 5, 12]

b)интервалом базового типа:

[25..45, 3..10] [‘a’..’d’, ‘k’..’n’]

c)выражениями базового типа:

[Ord(109),’s’] [Succ(3), Pred(9), Round(Sin(1.0))]

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

[‘a’, ‘b’, ‘c’]

[‘a’, ‘b’]

[‘a’, ‘c’]

[ ‘b’, ‘c’]

[‘a’]

[ ‘b’]

[ ‘c’]

[] пустое множество

а множество d - следующие:

[1, 2, 3, 4]

[1, 2, 3]

[1, 3, 4]

[1, 2, 4]

[2, 3, 4]

[1, 2]

[1, 3]

[1, 4]

[2, 3]

[2, 4]

[3, 4]

[1]

[2]

[3]

[4]

[]

Таким образом, любое множество может принимать 2ⁿ значений, где n – количество элементов в описании множества.

Порядок следования элементов во множестве не устанавливается, поэтому, например, значения множества [‘a’, ‘b’, ‘c’] и [‘b’, ‘c’, ‘a’] эквивалентны.

При работе со множествами в Паскале можно использовать следующие операции:

+ объединение (сумма) множеств,

* пересечение (произведение) множеств,

- разность множеств,

Inвхождение элемента во множество.

Пересечением двух множеств называется множество, состоящее из элементов, одновременно входящих в оба множества-сомножителя:

[3, 4, 5] * [1, 3, 5] = [3]

[3, 4, 5] * [3, 4, 5] = [3, 4, 5]

[2, 1, 0] * [] = []

[2, 9, 8] * [6, 7] = [] пустое множество

[‘a’, ‘b’, ‘c’] * [‘d’, ‘c’, ‘a’] = [‘a’, ‘c’]

Объединением двух множеств называется множество, состоящее из элементов, входящих хотя бы в одно из множеств-слагаемых:

[3, 4, 5] + [1, 3, 5] = [1, 3, 4, 5]

[2, 9, 8] + [] = [2, 9, 8]

[1, 2, 3] + [1, 2, 3] = [1, 2, 3]

[‘a’, ‘b’, ‘c’] + [‘d’, ‘c’, ‘a’] = [‘a’, ’b’, ‘c’, ‘d’]

Разностью двух множеств называется множество, состоящее из элементов множества-уменьшаемого без элементов множества-вычитаемого:

[3, 4, 5] – [1, 3, 5] = [4]

[2, 9, 5] – [3, 7] = [2, 9, 5]

[2, 4] – [5, 4, 2] = []

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

([3, 4, 5] + [1, 3, 6, 7]) * [5, 6, 7] – [6] = [5, 7]

Пример: в группе 12 студентов. Заданы множества номеров студентов:

1. множество спортсменов sport = [1, 2, 3, 4, 5]

2. множество отличников otl = [2, 3, 6, 7]

3. множество курящих smok = [7, 8]

1. множество спортсменов-отличников:

sport * otl = [1, 2, 3, 4, 5] * [2, 3, 6, 7] = [2, 3]

2. множество спортсменов или отличников:

sport + otl = [1, 2, 3, 4, 5] + [2, 3, 6, 7] = [1, 2, 3, 4, 5, 6, 7] = [1 . . 7]

3. множество курящих спортсменов:

sport * smok = [1, 2, 3, 4, 5] * [7, 8] = [] - пустое множество – спортсмены не курят!

4. множество некурящих отличников:

otl – smok = [2, 3, 6, 7] – [7, 8] = [2, 3, 6]

Для проверки вхождения какой-либо константы или переменной в определенное множество используется операция In , результатом которой является TRUE, если это значение входит во множество, и FALSE – если не входит:

5 In [1, 5, 7] = TRUE

‘b’ In [‘a’, ‘c’, ‘d’] = FALSE

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

A <= B равно TRUE, если все элементы множества A входят во множество B:

[5, 3, 2] <= [1, 2, 3, 4, 5] = True

A >= B равно TRUE, если все элементы множества B входят во множество A:

[‘d’, ‘e’, ‘f’, ‘g’] >= [‘d’, ‘g’] = True

A = B равно TRUE, если элементы этих множеств полностью совпадают:

[1, 2, 3] = [3, 2, 1] = TRUE

A <> B равно TRUE, если эти множества различаются хотя бы одним элементом:

[1, 2, 3] <> [5, 2, 1] = TRUE

Выражения со множествами, построенные с помощью операций *, + и - , могут быть использованы в операторах присваивания вида:

V := S;

где V – переменная-множество,

S – выражение со множествами того же типа.

Внимание! Элементы множеств нельзя вводить и выводить операторами Read и Write, то есть имя множества не должно появляться в списках операторов ввода-вывода.