Элементами множеств здесь могут быть числа, символы и булевы данные – то есть порядковые типы данных размером в один байт. Стало быть, мощность множеств в Паскале не превышает 256.
Объявление множеств
Множества объявляются конструкцией вида
SET OF <диапазон или тип>
Вот примеры объявления переменных типа множество.
{ объявление множества } { возможные элементы множества }
var SN1 : set of 10..100; { числа от 10 до 100 }
SN2 : set of byte; { числа от 0 до 255 }
SC1 : set of ’a’..’z’; { только малые латинские буквы }
SC2 : set of Char; { все символы }
Поскольку мощность множеств в Паскале не превышает 256, множества SET OF BYTE и SET OF CHAR представляют множества предельной мощности.
Присвоение значений множествам
Переменным типа множество присваивают значения выражений того же типа, вот примеры таких операторов.
SN1:= [10, 20, 50]; { содержит три элемента }
SN2:= [11..20, 51..60]; { содержит 20 элементов }
SN2:= [0..255]; { содержит 256 элементов от 0 до 255 }
SN2:= SN1; { копия другого множества }
SC1:= [’z’, ’y’, ’x’]; { содержит три элемента }
SC2:= [’0’..’9’]; { содержит 10 элементов }
Как видите, для записи множеств в Паскале используют квадратные скобки, а не фигурные. Что позволено в записи множеств, и что запрещено?
Подряд идущие элементы можно заменять диапазоном с указанием крайних значений. Допустимо перечислять элементы в произвольном порядке и даже вставлять дубликаты, – они все равно будут отброшены. Вот примеры трех совершенно одинаковых по результату операторов.
SN1:= [5..8]; { множество задано диапазоном }
SN1:= [8, 7, 6, 5]; { то же множество, но в другом порядке }
SN1:= [5..8, 6, 6]; { трижды указано число 6, дубликаты будут отброшены }
Множеству любого типа можно присвоить пустое значение, например:
SB1:= []; SN1:= []; SC1:= [];
Пустое множество изображается парой квадратных скобок, между которыми ничего нет. Нельзя считать пустым множество [0], поскольку оно содержит один элемент – число ноль.
Элементами множеств могут быть только значения переменных и выражений соответствующего типа.
var k, n : byte; c: char;
...
k:= 10; n:= 20;
SN1:= [1..k, n+5]; { 1..10, 25 }
c:= ’m’;
SC1:= [c, ’a’, ’b’]; { ’m’, ’a’, ’b’ }
Компилятор не позволит включать в множество элементы, не относящиеся к нему, а также смешивать элементы разных типов, вот примеры таких ошибок.
SN1:= [5..200]; { в объявлении SN1 указан диапазон от 10 до 100 }
SC1:= [’a’, ’b’, 5]; { вместо символа ’5’ указано число 5 }
Операции с множествами
В Паскале предусмотрены три известные вам вычислительные операции с множествами, а также сравнение множеств и проверка на вхождение элемента в множество.
Вычислительные операции – объединение, пересечение и вычитание – записывают на Паскале так:
SN2:= [3, 7] + [5, 2]; { объединение = [2, 3, 5, 7] }
SN2:= [2..10] * [8..20]; { пересечение = [8, 9, 10] }
SN2:= [2..10] – [8..20]; { разность = [2..7] }
Множества, объединенные знаками операций и круглыми скобками, образуют выражение, например:
SN2:= (SN1 + [0..15]) * SN2;
Выражения, составленные из множеств, очень похожи на выражения из чисел, но вычисляются по другим правилам. Это обманчивое сходство может спровоцировать ошибку – смешение в одном выражении чисел и множеств. Предположим, вы хотите добавить к множеству число, содержащееся в переменной K. Следующее выражение будет неверным.
SN1:= SN1 + K; { сложение множества с числом – ошибка }
Правильно будет так:
SN1:= SN1 + [ K ]; { добавляется множество из одного элемента }
Разумеется, за ошибками такого рода присматривает компилятор, проверьте его реакцию на практике.
Сравнение множеств
Множества можно сравнивать между собой, получая в результате булево значение – TRUE или FALSE.
Два множества равны, если содержат одни и те же элементы.
if SN1 = SN2 then … else …
Множества неравны, если одно из них содержит, хотя бы один элемент, которого нет в другом.
if SN1 <> [15, 17, 19] then … else …
Проверка на подмножество (<=) отвечает на вопрос: все ли элементы первого множества входят во второе?
if SN1 <= SN2 then … else …
Проверкой на надмножество (>=) выясняют, все ли элементы второго множества входят в первое.
if SN1 >= SN2 then … else …
Проверка на вхождение элемента в множество (операция IN)
Входит ли некоторый элемент в множество? Это можно выяснить так:
var N : byte; S : set of byte;
...
if ([N] * S) <> [] then { N входит в S } else { не входит }
Понятно, что, если число N входит в множество S, то пересечение [N]*S не будет пустым. Но проще выяснить это операцией IN – она введена специально для этого. Операция дает TRUE, если значение перечислимого типа входит в данное множество, например:
if N in S then { N входит в S } else { не входит }
if 20 in S then { 20 входит в S } else { не входит }
Решение директорской задачи
Вернемся к временно покинутому директору Семену Семеновичу. Напомню стоящую перед нами задачу: есть текстовый файл, каждая строка которого содержит список номеров учеников, состоящих в некотором кружке.
2 11 4 13
9 17 12 11 3 5 18
14 2 13 15 20
Надо составить список нигде не числящихся разгильдяев.
Можно ли воспринимать эти списки как множества? Вероятно, да, судите сами:
• каждый список содержит номер ученика не более одного раза (ошибочные повторные записи все равно отбросят);
• порядок следования в списке не важен;
• список может быть пустым (если никто не записался в этот кружок).
Хорошо, а будет ли множеством список всех учеников школы? Конечно. Такое множество будет полным, поскольку содержит все возможные элементы. А раз так, директорскую задачку решим через множества.
Множество тех, кто записался хотя бы в один кружок, найдем объединением отдельных множеств-кружков (S1 + S2 + S3). Вычтя это объединение из полного множества учеников, получим множество уклонившихся. Вот и все решение! На Паскале это запишется так:
