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). Вычтя это объединение из полного множества учеников, получим множество уклонившихся. Вот и все решение! На Паскале это запишется так:
var R, S1, S2, S3 : set of 1..250;
begin
S1:= [ 2, 11, 4, 13 ]; { 1-й кружок }
S2:= [ 9, 17, 12, 11, 3, 5, 18 ]; { 2-й кружок }
S3:= [ 14, 2, 13, 15, 20 ]; { 3-й кружок }
R:= [1..250] – (S1 + S2 + S3); { R – множество уклонившихся }
end.
Выделеное выражение в скобках – это множество учеников, состоящих хотя бы в одном кружке. Итак, решение задачи вместилось в одну строчку! Нет, не зря мы терпели математика и корпели над множествами!
Показанное выше решение – это работающая программа, которую можно запустить в пошаговом режиме, и через отладчик увидеть результат. Сделайте это. А как быть с вводом и выводом множеств? Ведь исходные данные хранятся в файле, а результат – переменную R – тоже надо вывести в файл или на экран. Вот этим мы и займемся в следующей главе.
Итоги• Множества – это инструмент, взятый в Паскаль из математики.
• В Паскале применяют конечные множества, элементами которых могут быть числа, символы и булевы значения. Мощность множеств в Паскале не превышает 256.
• В Паскале предусмотрен ряд операций с множествами: объединение, пересечение, вычитание, сравнение, а также проверка на вхождение элемента в множество.
• Сравнение двух множеств дает булев результат, который используют в условных и циклических операторах.
• Операция IN – удобное средство для проверки вхождения одного элемента в множество, она тоже дает булев результат.
А слабо?А) Найдите ошибки в следующих операторах.
type TNumbers = set of 1..300;
TChars = set of char;
TBytes = set of byte;
var c1, c2 : TChars;
b1, b2 : TBytes;
begin
c1:= [1..9];
c2:= ['1'..'9'];
c2:= c2 + ’0’;
c2:= c2 + [0];
b1:= c1;
b2:= b1 + [1,7,3];
Writeln(b1=b2);
Writeln(1 in b2);
Writeln([1] in b2);
Writeln(b1 in b2);
end.
Б) Напечатайте 20 случайных чисел в диапазоне от 1 до 50 так, чтобы каждое число встретилось в распечатке лишь по разу. Подсказка: после генерации числа функцией Random проверьте его на вхождение в множество уже напечатанных чисел.
В) Введите программу решения директорской задачи (см. предыдущую страницу), а затем запустите её в пошаговом режиме (клавишей F7). Перед запуском вставьте все переменные в окно обзора переменных «Watch» и проследите за их изменением. Напомню, что о средствах отладки рассказано в главе 21.
Глава 37Ввод и вывод множеств
Мы узнали о множествах и приспособили их к директорской задаче. Чтобы покончить с нею доделаем ещё пару пустяков: организуем ввод и вывод множеств. Для ввода-вывода строк и простых типов данных годятся процедуры Read[ln] и Write[ln]. Но сейчас все не так просто, – эти процедуры не способны работать, ни с множествами, ни с другими сложными типами данных. Однако ж «нормальные герои всегда идут в обход», – пойдем так и на этот раз.
Вывод множества в текстовый файлНачнем с вывода числового множества на экран (или в файл, – что одно и то же). Так мы получим средство для последующей проверки вводимых множеств.
Раз уж процедура Writeln не печатает множество одним махом, выведем каждый его элемент по отдельности – ведь это обычные числа или символы. Проверяя все возможные элементы множества, будем печатать лишь те, что входят в него – в этом основная идея. Напомню, что для такой проверки подходит операция IN. Дополнив её циклом со счетчиком, соорудим несложную процедуру распечатки числового множества. Вот она вместе с программой для её проверки.
{ P_37_1 – вывод множества в файл }
type TSet = set of 1..255; { объявление типа «множество» }
{----- Процедура вывода множества в файл -----}
procedure WriteSet(var aFile: text; const aSet : TSet);
var k : integer;
begin
for k:=1 to 255 do { цикл по всем элементам множества}
if k in aSet { если K входит в множество }
then Write(aFile, k:4); { печатаем в строке }
Writeln(aFile); { по окончании – переход на следующую строку }
end;
{----- Программа для проверки процедуры WriteSet -----}
var S1 : TSet; F: text;
begin
Assign(F, ''); Rewrite(F); { связываем файл с экраном! }
S1:= [3, 10, 25]; { значение множества }
WriteSet(F, S1); { печатаем }
Readln;
Close(F);
end.
В первой строке объявлен тип данных TSet, он может содержать целые числа от 1 до 255. Процедура распечатки WriteSet принимает по ссылке два параметра: файловую переменную и множество, которое надо распечатать. Внутри процедуры работает цикл FOR, перебирающий все возможные элементы множества. Те из них, что содержатся в нём, печатаются в текущей строке. По завершении цикла оператор Writeln переводит позицию записи на следующую строку файла.