Множеством называется совокупность однотипных элементов, рассматриваемых как единое целое. Множество может содержать от 0 до 255 элементов.
В отличие от элементов массива элементы множества не пронумерованы, не упорядочены. Каждый отдельный элемент множества не идентифицируется, и с ним нельзя выполнить какие-либо действия. Действия могут выполняться только над множеством в целом. Тип элементов множества может быть любым перечисляемым за исключением типа Real.
Конкретные значения множества - список элементов, заключенный в квадратные скобки. [3,4,1,9,12] — множество из пяти целых чисел;
[1.. 100] — множество целых чисел от 1 до 100;
['а','b','с'] — множество, содержащее три литеры а, b, с;
[' а '.. ' 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;
Нельзя вводить значения во множественную переменную оператором ввода и выводить оператором вывода. Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания
A:=[50, 100, 150, 200]; B:=[‘d’,’f’,’r’]; C:=[true,false]; D:=A;
Кроме того, выражения могут включать в себя операции над множествами.
Операции над множествами. В Паскале реализованы основные операции теории множеств. Это объединение, пересечение, разность множеств. Во всех таких операциях операнды и результаты есть множественные величины одинакового типа.
Объединение множеств. Объединением двух множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Знак операции объединения в Паскале +.
Например: [1,2,3,4] + [3,4,5,6]-» [1,2,3,4,5,6]
Пересечение множеств. Пересечением двух множеств А и В называется множество, состоящее из всех элементов принадлежащих, одновременно множеству А и множеству В. Знак операции пересечения в Паскале *.
Например: [1,2,3,4]*[3,4,5,6]=[3,4]
Разность множеств. Разностью двух множеств А к В называется множество, состоящее из элементов множества А, не принадлежащих множеству В.
Например: [1,2,3,4]-[3,4,5,6]->[1,2] [3,4,5,б]-[1,2,3,4]-»[5,6]
Операции отношения. Множества можно сравнивать между собой, т. е. для них определены операции отношения. Результатом отношения, как известно, является логическая величина true или false. В таблице описаны операции отношения над множествами. Предполагается, что множества Аи Б содержат элементы одного типа.
|
|
Отношение | Результат | |
True | False | |
А = В А<>В А<=В А>=В | Множества А и В совпадают Множества А и В не совпадают Все элементы А принадлежат В Все элементы В принадлежат А | В противном случае В противном случае В противном случае В противном случае |
Операция вхождения. Это операция, устанавливающая связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества.
х In М
Результат — логическая величина true, если значение х входит в множество M, и false — в противном случае.
Рассмотрим несколько задач, для решения которых удобно использовать множества.
Пример 1. Дана символьная строка. Подсчитать в ней количество знаков препинания (.-,;:!*?).
Program PI;
Var S: String; I,K: Byte; Begin
ReadLn(S); K:=0; For I:=l To Length(S) Do
If S[I] In ['.',' -',',',';',':','!,'*,'?'] Then K:=K+1;
WriteLn('Число знаков препинания равно’,К) End.
В этом примере использована множественная константа с символьным типом элементов. Эту задачу можно решить и без множества, записав в операторе if длинное логическое выражение: (S[i] = '.') Or (s [ i ] = ' — ') и т.д. Использование множества сокращает запись.
Пример 2. Даны две символьные строки, содержащие только строчные латинские буквы. Построить строку S3, в которую войдут только общие символы S1 и S2 в алфавитном порядке и без повторений.
Program Р2;
Type Mset=Set Of ' а'.. ' z ';
Var SI,S2,S3: String;
MS1,MS2,MS3: Mset;
a: Char;
Begin {Ввод исходных строк}
ReadLn(Sl);ReadLn(S2);MS:=[]; {Формирование множеств MSI и MS2}
For I:=l To Length(S1) Do MS1:=MS+[S1[I]];
For I:=l To Length(S2) Do MS2:=MS+[S2[I]];
MS3:=MS1*MS2; {Пересечение множеств}
For a:=’a’ To ‘z’ Do If a in MS3 Then writeln(a);
end;
Контрольные вопросы по теме «Множества»
1. Дайте определение типа «Множество».
2. Какие ограничения накладываются на тип данных из множеств
3. Опишите тип «Множество».
4. Назовите основные операции над множествами.
5. Опишите способы ввода, вывода данных множества.