Песни о Паскале - [72]

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). Вычтя это объединение из полного множества учеников, получим множество уклонившихся. Вот и все решение! На Паскале это запишется так:

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 – тоже надо вывести в файл или на экран. Вот этим мы и займемся в следующей главе.