3.18. Понятие множества. Множественный тип данных

Одним из фундаментальных разделов математики является теория множеств. Некоторые моменты математического аппарата этой теории реализованы в Паскале через множественный тип данных (множества).

Множеством называется совокупность однотипных элементов, рассматриваемых как единое целое. В Паскале могут быть только конечные множества. В Турбо Паскале множество может содержать от 0 до 255 элементов.

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

Тип элементов множества называется базовым типом. Базовый тип может быть любым скалярным, за исключением типа Real.

Конструктор множества. Конкретные значения множества задаются с помощью конструктора множества, представляющего собой список элементов, заключенный в квадратные скобки. Сами элементы могут быть либо константами, либо выражениями базового типа. Вот несколько примеров задания множеств с помощью конструктора:

[3,4,7,9,12] — множество из пяти целых чисел;

[1.. 100] — множество целых чисел от 1 до 100;

['a','b','c'] — множество, содержащее три литеры а, Ь, с;

['a'.,'z','?','!'] — множество, содержащее все прописные латинские буквы, а также знаки ? и !.

Символы [] обозначают пустое множество, т.е. множество, не содержащее никаких элементов.

Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1,2,3] и [3,2,1] эквивалентные множества.

Каждый элемент в множестве учитывается только один раз. Поэтому множество [1,2,3,4,2,3,4,5] эквивалентно [1.. 5 ].

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

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

Например:

Var A,D: Set Of Byte;

В: Set Of ' a' . . ' z;

C: Set Of Boolean;

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

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

Например:

А:=[50,100,150,200];

B:=['m', 'n','k'];

С:=[True,False] ;

D:=A;

Кроме того, выражения могут включать в себя операции над множествами.

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

Объединение множеств. Объединением двух множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Знак операции объединения в Паскале +.

На рис. 34, а схематически показан результат объединения двух множеств.

Например:

[1,2,3,4]+[3,4,5,6]→[1,2,3,4,5,6]

Пересечение множеств. Пересечением двух множеств А и В называется множество, состоящее из всех элементов принадлежащих, одновременно множеству А и множеству В (см. рис. 34, б) Знак операции пересечения в Паскале *.

Например:

[1,2,3,4]*[3,4,5,6]→[3,4]

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

Например:

[1,2,3,4]-[3,4,5,6]→[1,2]

[3,4,5,6]-[1,2,3,4]→[5,6]

Очевидно, что операции объединения и пересечения — перестановочны, а разность множеств — не перестановочная операция.

Операции отношения. Множества можно сравнивать между собой, т.е. для них определены операции отношения. Результатом отношения, как известно, является логическая величина true или false. Для множеств применимы все операции отношения, за исключением > и <. В таблице описаны операции отношения над множествами. Предполагается, что множества А и В содержат элементы одного типа.

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

Var М: Set Of Byte;

В разделе операторов ей присваивается значение:

М:=[3,4,7,9];

Тогда операции отношения дадут следующие результаты:

М=[4,7,3,3,9]        - true,

М<>[7,4,3,9]         - false,

[3,4]<=М             - true,

[]<=M                — true,

M>=[1..10]           - false,

M<=[3..9]            - true.

Операция вхождения. Это операция, устанавливающая связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества. Если х — такая скалярная величина, а M — множество, то операция вхождения записывается так:

X In M

Результат — логическая величина true, если значение х входит в множество M, и false — в противном случае. Для описанного выше множества

4 In M — true,

5 In М - false.

Рассмотрим несколько задач, для решения которых удобно использовать множества.

Пример 1. Дана символьная строка. Подсчитать в ней количество знаков препинания (. - , ; : ! * ?).

Program P1;

Var S: String; I,K: Byte;

Begin

ReadLn(S); K:=0;

For I:=1 To Length(S) Do

If S[I] In ['.','-',',',';',':', '!', '*','?']

Then K:=K+1;

WriteLn('Число знаков препинания равно',К)

End.

В этом примере использована множественная константа с символьным типом элементов. Эту задачу можно решить и без множества, записав в операторе If длинное логическое выражение: (S[l]='.') Or (S[l]='-') и т.д. Использование множества сокращает запись.

Пример 2. Даны две символьные строки, содержащие только строчные латинские буквы. Построить строку S3, в которую войдут только общие символы S1 и S2 в алфавитном порядке и без повторений.

Program Р2;

Type Mset=Set Of 'a'..'z';

Var S1,S2,S3: String;

MS1,MS2,MS3: Mset;

C: Char;

Procedure SM(S: String; Var MS: Mset);

{Процедура формирует множество MS, содержащее все символы строки S}

Var I: Byte;

Begin MS:=[] ;

For I:=1 To Length(S) Do

MS:=MS+[S[I]]

End;

Begin {Ввод исходных строк)

ReadLn(S1);ReadLn(S2);

{Формирование множеств MS1 и MS2 из символов строк S1 и S2)

SM(S1,MS1);SM(S2,MS2);

{Пересечение множеств - выделение общих элементов в множество MS3}

MS3:=MS1*MS2;

{Формирование результирующей строки S3)

S3:=";

For С: ='а' То 'z' Do

If С In MS3 Then S3:=S3+C;

WriteLn('Результат:',S3)

End.

Пример 3. Составить программу, по которой из последовательности натуральных чисел от 2 до N (1 < N ≤ 255) будут выбраны все простые числа.

Для решения задач такого типа существует алгоритм, известный под названием «Решето Эратосфена». Суть его в следующем:

1. Из числовой последовательности выбираем минимальное значение, это будет простое число.

2. Удаляем из последовательности все числа, кратные выбранному.

3. Если после удаления последовательность не стала пустой, то возвращаемся к выполнению пункта 1.

Вот пример работы такого алгоритма для N = 15 (подчеркнуты выбранные простые числа):

2 3 4 5 6 7 8 9 10 11 12 13 14 15

3 5 7 9 11 13 15

5 7 11 13

7 11 13

11 13

13

Решение этой задачи удобно программировать, используя множественный тип.

Program Eratosfen;

Const N=201;

{Возможно любое значение 1

Var А,В: Set Of 2..N;

K,P: Integer;

Begin

{Формирование исходного множества А; В - искомое множество простых чисел, сначала - пустое}

A:=[2..N]; В:=[]; Р:=2;

Repeat

{Поиск минимального числа в множестве А}

While Not(P In A) Do Р:=Р+1;

{Включение найденного числа в множество В)

В:=В+[Р];

К:=Р;

{Исключение из А чисел, кратных Р}

While K<=N Do

Begin

A:=A-[K];

K:=K+P;

End

Until A= [ ] ;

{Вывод результата, т.е. всех чисел из множества В в порядке возрастания}

For Р:=2 То N Do If P In В Then WriteLn(P)

End.

Красивая программа! К сожалению, ею нельзя воспользоваться для N > 255 из-за отмеченного выше ограничения на максимальный размер множества в Турбо Паскале.

Пример 4. Как уже говорилось, нельзя вводить значения непосредственно в множество. Однако такая потребность у программиста может возникнуть. В этом случае можно прибегнуть к процедуре INSET, описанной ниже. Для примера рассматривается множество с символьным базовым типом. Предполагается, что в основной программе глобально объявлен тип SetChar.

Type SetChar: Set Of Char;

Procedure INSET(Var M: SetChar);

Var I,N: Byte; C: Char;

Begin

Write('Укажите размер множества:'); ReadLn(N);

M:=[];

For I:=l To N Do

Begin

Write(1:1,'-и элемент:'); ReadLn(С);

M:=M+[C]

End;

WriteLn('Ввод завершен!')

End.

В основной программе для ввода значений в множество, например с именем sim, достаточно записать оператор: INSET (SIM);

Произойдет диалоговый ввод значений.