Лабораторная работа № 5. Множества

Описание типа «множество»

Множество - структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа «множество» - набор всевозможных подмножеств, составленных из элементов базового типа. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов множества называется его мощностью.

Для описания множественного типа используется сочетание set of (множество из…). Синтаксическая диаграмма множественных типов имеет следующий вид:

 

set

of

тип

Изображение множества:

 

 

[

выражение

]

выражение

..

,

Элементы множества не пронумерованы, не упорядочены. Каждый отдельный элемент множества не идентифицируется, и с ним нельзя выполнить какие-либо действия. Действия могут выполняться только над множеством в целом.

 

Конструктор множества

 

Конкретные значения множества задаются с помощью конструктора множества, представляющего собой список элементов, заключенный в квадратные скобки.[3,4,7,9,12] – множество из пяти целых чисел; [1..100]-множество целых чисел от 1до 100;

Переменные множественного типа описываются так:

Var <идентификатор>: set of <базовый тип >

Например:

Var A, D: set of byte;

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

<множественная переменная >:=<множественное выражение>

 

 

Операции над множествами

 

При работе с множествами допускается использование операций отношения =, <>, >=, <=, обледенения, пересечения, разности, множеств и операции in. Результатом выражений с применением этих операций является значение True или False.

 

Примеры:

1. [1, 2, 4] = [1, 4, 2] // Результат True

2. ['a'.. 'z'] = ['a'.. 'p'] // Результат False

3. [1, 2, 5, 6] <> [1, 2] // Результат True

4. ['a', 'b', 'c'] <= ['a'.. 'z'] // Результат True

5. ['a'.. 'k'] >= ['a'.. 'z'] // Результат False

6. [1, 2, 3] + [1, 4, 5] // Результат [1, 2, 3, 4, 5]

7. [1, 2, 3] * [1, 3, 4, 5] // Результат [1, 3]

8. [1, 3, 4, 5] - [1, 4, 6] // Результат [3, 5]

 

Операция «равно» (=). Два множества А и В считаются равными, если они состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.

Например:

[1,2,3,4] [1,2,3,4] A=B True [‘a’,’b’,’c’] [‘c’,’a’] A=В False. [‘a’..’z’] [‘z’..’a’] A=B True

Значение А Значение В Выражение Результат

Операция «не равно» (<>). Два множества А и В считаются не равными, если они отличаются по мощности или по значению хотя бы одного элемента.

Например:

Значение А Значение В Выражение Результат

[1,2,3,] [3,1,2,4] A<>B True [‘a’..’z’] [‘b’..’z’] A<>B True [‘c’..’t’] [‘t’..’c’] A<>B False.

 

 

Операция «больше или равно» (>=). Эта операция используется для определения

принадлежности множеств. Результат операции А>=B равен True, если все элементы

множества В содержатся в множестве А. В противном случае результат равен False.

Например:

Значение А Значение В Выражение Результат

[1,2,3,4] [2,3,4] A>=B True [‘a’..’z’] [‘b’..’t’] A>=B True [‘z’,’x’,’c’] [‘c’,’x’] A>=B True

 

Операция «меньше или равно» (<=). Эта операция используется аналогично предыдущей операции, но результат выражения A<=B равен True, если все элементы множества А содержатся в множестве В. В противном случае результат равен False.

Например:

 

Значение А Значение В Выражение Результат

[1,2,3,] [1,2,3,4] A<=B True [‘b’..’h’] [‘z’..’a’] A<=B True [‘a’,’v’] [‘a’,‘n’,’v’] A<=B True

Пример.

 

 

Операция in. Эта операция используется для проверки принадлежности какого-либо значения указанному множеству. Обычно применяется в условных операторах.

Например:

Значение А Выражение Результат

2 if A in [1,2,3] then… True ‘v’ if A in [‘a’..’n’] then… False x 1 if A in [x0,x1,x2,x3] then… True

 

 

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

Первым операндом, стоящим слева от слова in, является выражение базового типа. Второй операнд, стоящий справа от слова in, должен иметь множественный тип, например:

a in [a, b, c, d] // Результат True

2 * 4 in [0.. 4, 7.. 10] // Результат True

'a' + 'b' in ['ab', 'cd', 'ef'] // Результат True

5 in [1 * 2, 4, 5] // Результат True

5 in [2, 4, 6, 8] // Результат False

 

Операция in позволяет проводить эффективно сложные проверки условий. Например, вместо:

(c >= '0') and (c <= '9') or (c >= 'a') and (c <='z');

Проще записать:

c in ['0'.. '9', 'a'.. 'z'];

 

Причём последняя конструкция будет, как правило, более эффективной.

Операции (=) и (<>) позволяют проверить, равны ли два множества или нет. С помощью операций (>=) и (<=) можно определить, является ли одно множество подмножеством другого. Пример:

[red, white] = [red, green] // Результат False

[1] <= [0.. 4] // Результат True

Замечания:
1. Пустое множество [ ] является подмножеством любого другого множества независимо от базового типа его элементов.
2. Множества-операнды могут иметь непересекающиеся базовые типы. Располагая, например, множествами A: set of 1.. 99 и B: set of 100.. 150, можно в результате объединения A+B получить новое множество с базовым типом 1.. 150.

3. Следует различать конструктор множества [X.. Y] и отрезок порядкового типа X.. Y. При X > Y в первом случае речь идёт о пустом множестве, а во втором компилятор выдаст ошибку. Пример:

['a', 'b'] = ['b'.. 'a'] // Результат Fals

При проверке на подмножество выполняется тест на "меньше или равно", а не только проверка на собственное подмножество, т.е без "равно". Операции (<) и (>) не предусмотрены, поэтому при необходимости проверку на собственное подмножество для множеств A и B можно провести следующим образом:

(A <= B) and (A >= B) или (A >= B) and (A <> B)

Объединение множеств (+). Объединением двух множеств является третье множество, содержащее элементы обоих множеств.

Например:

 

[1,2,3,] [1,4,5] A+B [1,2,3,4,5] [‘А’..’D’] [‘E’..’Z’] A+В [‘A’..’Z’] [ ] [ ] A+B [ ]

Значение А Значение В Выражение Результат

Пересечение множеств (*). Пересечением двух множеств является третье множество, которое содержит элементы, входящие одновременно в оба множества.

Например:

Значение А Значение В Выражение Результат

[1,2,3,] [1,4,2,5] A*B [1,2] [‘A’..’Z’] [‘B’..’R’] A*B [‘B’..’R’] [ ] [ ] A*B [ ]

 

 

Разность множеств (-). Разностью двух множеств является третье множество, которое содержит элементы первого множеств, не входящее во второе множество.

 

Например:

Значение А Значение В Выражение Результат

[1,2,3,4] [3,4,1] A – B [2] [‘A’..’Z’] [‘D’..’Z’] A – B [‘A’..’C’] [x1,x2,x3,x4] [x4,x1] A – B [x2,x3]

Результат операций над двумя множествами можно наглядно представить с помощью закрашенных частей двух прямоугольников: