Общие сведения. Множество – это тип данных, имеющий определенную структуру, представляющий набор взаимосвязанных по какому-либо признаку или группе признаков объектов

Множество – это тип данных, имеющий определенную структуру, представляющий набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект во множестве называется элементом множества. Область значений типа множества – набор всевозможных подмножеств, составленных из элементов полного множества. Если множество имеет N значений, то тип множества для него будет иметь 2 в степени N вариантов различных значений. В выражениях на языке Паскаль значения элементов множества указываются в квадратных скобках: [1,2,3,4], [‘a’,’b’,’c’,], [‘a’, ‘z’].

Если множество не имеет элементов, то оно называется пустым и обозначается как [ ].

Количество элементов множества не должно превышать 256, а номера значений базового типа должны находится в диапазоне 0..255.

Порядок, в котором указываются элементы множества, не имеет значения. Тип множества определяется не порядком, в каком пронумерованы элементы множества, а тем, какие элементы оно включает.

Так множества A и B, заданные следующим образом

A: =[1,2,3,4,5]

B: =[2,3,1,4,5]

Фактически отличаются друг от друга только именами.

Все элементы множества должны принадлежать одному из скалярных типов, например, CHAR или ограниченному типу, созданному на основе типа INEGER; но не могут принадлежать вещественному типу. Этот тип называется базовым типом множества и задается диапазоном или перечислением.

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

1) с предварительным описанием типа:

TYPE <имя типа>= SET OF <список элементов множества>

VAR <список переменных>: <имя типа>

Например:

TYPE

PROSTOE=SET OF (3,5,7);

VAR

DR: PROSTOE;

В данном примере тип PROSTOE описан как множество, состоящее из трех простых чисел (N=3) 3,5,7. А переменная DR, имеющая тип PROSTOE может принимать 2³=8 значений, являющихся подмножествами множества, состоящего из простых чисел 2,5,7: [], [3], [5], [7], [3,5], [5,7], [7,3], [3,5,7];

2) без предварительного описания типа

Например:

VAR

PR: SET OF (3,5,7)

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

Над множествами выполняют следующие операции:

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

Пример:

A: =[1,2,3];

B: =[1,4,5];

C: =A+B;

В результате выполнения этой группы операторов множество C получит значение [1,2,3,4,5];

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

Пример 1:

A: =[1,2,3,4];

B: =[1,4,5];

C: =[A*B];

В результате пересечения множество C получит значение [3,4]

Пример 2:

A: =[‘A’..’Z’];

B: =[‘B’..’R’];

C: =A*B;

Множество C получит значение [‘B’..’R’].

В последнем примере множества A и B заданы диапазонам.

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

Пример:

A: =[X1,X2,X3,X4];

B: =[X4,X1];

C: =A-B;

Множество C получит значение [X2,X3].

Множества можно сравнивать между собой с помощью инструкции IF. При этом можно использовать следующие операции отношения:

= равно

не равно

<= содержится в

Так, например, выражение IF A=B THEN… означает: “если все элементы множества A является также и элементами множества B и наоборот, то…”

Выражение IF A<>B показывает, что обращается внимание на то, имеется ли различие между множествами A и B.

В выражении IF A<=B THEN проверяется, все ли элементы множества A являются также элементами множества B, но не наоборот. Говорят, что множество A включается в множество B.

Кроме выше перечисленных операций отношения, в работе с множествами используется оператор IN. Так запись

IF K IN C THEN…

Означает: если данный элемент K находится во множестве C, то выполняй операторы следующие за THEN.

Рассмотрим примеры:

Пример 1: Определить, сколько элементов массива A(4, 5)

Являются элементами множества B.

1 PROGRAM PT;

2 VAR

A: ARRAY [1..4, 1..5] OF INTEGER;

B: SET OF 1..10;

I, J, K: INTEGER;

BEGIN

7 B: = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

8 K: =0;

9 FOR I: =1 TO 4 DO

10 FOR J: = TO 5 DO

11 BEGIN

12 READ (A [I, J]);

13 IF A[I, J];

14 END;

15 WRITE (K);

16 END.

В программе в строках 2-5 описываются переменные и массивы, с которыми работает программа, а также множество B. В строке 7 при помощи оператора присваивания задается значение множества B. В строке 8 задается первоначальное значение счетчика количества элементов массива A, являющихся одновременно элементами множества B. В строках 9-14 задается соответственно в циклах по I и J ввод значений элементов массива A с последующей проверкой на их принадлежность множеству B. В 15 на печать выводится результат подсчета.

Пример 2: Объединить два списка людей, исключив из него всех однофамильцев. Списки включают по 10 человек. Новый список вывести на печать. При решении задачи считать, что каждая фамилия кодируется одной буквой.

1 PROGRAM OB;

2 VAR

S1, S2, S: SET OF CHAR;

N1, N2, CHAR;

SP1, SP2: ARRAY [1..10] OF CHAR;

I: INTEGER;

BEGIN

8 S1: = []; S2: = [];

9 FOR I: =1 TO 10 DO BRGIN

10 READ (N1, N2); S1: =S1+[N1];

11 S2: =S2+[N2]; SP1 [I]: =N1;

12 SP2: =N2; END;

13 S: =S1*S2;

14 S: =S1+S2-S;

15 FOR I: =1 TO 10 DO

16 BEGIN

17 IF SP1 [I] IN S THEN WRITE (SP1[I]);

18 IF SP2 [I] IN S THEN WRITE (SP2[I]);

19 END;

20 END.

В программе в строках 2 – 6 описываются переменные и массивы, с которыми работает программа. S1 и S2 первый и второй списки, - третий объединённый список.

В 8 первоначальные значения множеств приравниваются кпустому множеству. В строках 9 – 12 вводятся по вспомогательным переменным и фамилии по обоим спискам и заносятся в множества и вспомогательные массивы. В 13 определяется пересечение множеств, т. е. фамилии однофамильцев. В 14 определяется объединение множеств и из него отнимаются фамилии однофамильцев. В строках 15-19 в цикле по I определяется принадлежность элементов массивов к множеству и при выполнении условия принадлежности результат выводится на печать. По окончании работы программы на печать будет выведен объединённый список за исключением фамилий однофамильцев.

Контрольные вопросы

1. Что такое множество?

2. Порядок описания множеств.

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

4. Порядок использования оператора IN.

5. Какого типа бывают множества?