Множества

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

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

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

Под множествомв Паскале понимается неупорядоченный набор фиксированного количества (не более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.заданием множества как типизированной константы:

Const r : 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, то есть имя множества не должно появляться в списках операторов ввода-вывода.