 |
Понятие множества. Операции над множествами
|
|
|
|
В программировании структура, состоящая из элементов одного типа, которые можно по-разному располагать, называется множеством. Общий вид описания переменной множественного типа в языке Паскаль:
Var
< имя_множества >: set of < тип >;
где var и set – служебные слова. Слово set в переводе с английского и означает «набор, множество»;
< имя_множества > – имя создаваемого типа-множества;
< тип > – один из уже существующих типов, к которому относятся элементы вновь создаваемого множества.Если набор элементов множества представляет собой какой-либо отрезок значений одного из порядковых типов, то можно указать только начальное и конечное значение, а между ними поставить символ «..». Если же элементы, составляющие множество не идут подряд в базовом типе, то эти элементы нужно перечислить в скобках через запятую.
Примеры описания множеств:
Множество натуральных трехзначных чисел:
Var
triznak: set of 100..999;
Базовый тип для данного множества – integer.
Множество прописных букв русского алфавита
Var
prop: set of 'А’..’Я’;
Базовый тип – char.
При описании множества элементы множества не должны повторяться и если множество создается на базе числового типа данных, то значения элементов множества не должны быть с одной стороны отрицательными, а с другой - не превышать число 255.
Наряду с вышеописанными переменными типа «множества» в программах могут встречаться и постоянные множества. Элементы такого множества перечисляются в квадратных скобках: [1,2,3,4,5,6,7,8,9] – так будет выглядеть описание постоянного множества, состоящего из однозначных целых чисел. Множество, может содержать несколько элементов, один элемент – [1] или вообще ни одного – []. В последнем случае множество называется пустым.
|
|
|
Над множествами, так же как и над обычными переменными, можно выполнять ряд операций.
Операция, обозначающаяся знаком * – пересечение двух множеств. Результатом выполнения этой операции над двумя множествами является нахождение их общих элементов, принадлежащих как одному, так и другому множеству. Например, если мы присвоим переменной типа «множество» А значение [20,30,40], что записывается в программе следующим образом: А:=[20,30,40];
а переменной того же типа B присвоим значение [30,40,50], что записывается как B:=[30,40,50];
то в результате операции C:=A*B множество С получит следующее значение – [30,40].
Если при операции над двумя множествами используется знак +, то такая операция называется объединением двух множеств. Результатом такой операции будет получение множества, в которое будут входить все элементы, содержащиеся хотя бы в одном из исходных множеств. В качестве примера возьмем два множества: lat, значением которого будет [q,w,e,r,t,y] и rus, значением которого будет [й,ц,у,к,е,н,г]. В результате операции latrus:=lat+rus множество
latrus получит следующее значение: [q,w,e,r,t,y, й,ц,у,к,е,н,г].
Операция, обозначаемая знаком – называется разностью двух множеств. В результате выполнения данной операции над двумя множествами мы получаем новое множество, содержащее те элементы первого, которые не входят во второе. Рассмотрим эту операцию на примере двух множеств language и low. Первому из этих множеств присвоим значение, представляющее собой перечень различных языков программирования, а второе представляет собой список только тех языков, которые не являются языками высокого уровня. Операции присваивания будут выглядеть следующим образом:
language:=[basic,pascal,c,fortran,algol,assembler_language,machine_code];
low:=[assembler_language,machine_code];
Далее, выполним операцию нахождения разности и результат присвоим множеству high:
high:=language-low;
|
|
|
в результате данной операции множество high получит следующее значение: [basic,pascal,c,fortran,algol], то есть данное множество будет содержать в себе перечень языков высокого уровня.
Наряду с вышеописанными операциями над множествами можно также производить сравнение множеств друг с другом. В сравнении также участвуют два множества. Для сравнения двух множеств используются операции отношения, которые обозначаются теми же знаками, что и операции сравнения обычных переменных, но имеют иной смысл. Результатом операции отношения является логическая величина, которая может принимать значения true или false. Рассмотрим более подробно данные операции:
= - равенство двух множеств (все элементы первого множества совпадают с элементами второго);
< > - неравенство двух множеств (одно из множеств содержит хотя бы один элемент, отсутствующий в другом).
Пример использования данных операций: даны два множества G и H. Значение множества G – [4,5,6]; H также имеет значение [4,5,6]. Для данных множеств результат операции сравнения G = H будет равен true, а операции G < > H будет равен false. В случае же, если мы множеству H присвоим другое значение H:=[6,7,8]; а G оставим без изменения, то результат операции G = H будет равен false, а операции G < > H будет равен true.
< - проверка на строгое вхождение первого множества во второе (то есть все элементы первого множества должны одновременно входить во второе. Кроме того, второе множество должно содержать какие-либо дополнительные элементы.)
<= - проверка на нестрогое вхождение первого множества во второе (все элементы первого множества должны одновременно входить во второе. Помимо элементов первого множества второе множество может как содержать, так и не содержать какие-либо дополнительные элементы.)
> - проверка на строгое вхождение второго множества в первое;
>= - проверка на нестрогое вхождение второго множества в первое.
При работе с множествами часто используется еще одна операция, в которой участвуют не два множества, а множество и какой-либо элемент. Такая операция называется операцией определения принадлежности элемента множеству. Общий вид данной операции следующий:
< элемент > in [< значение_множества >];
где < элемент > – элемент, относящийся к базовому для данного множества типу;
|
|
|
in – служебное слово, обозначающее в переводе с английского «в»;
< значение_множества > – список всех элементов, входящих в множество. Операция имеет значение true, если элемент входит в данное множество (то есть совпадает с одним из элементов множества) и false, если он в данное множество не входит.
Например, выражения D in [ A..E] и 5 in [3,5,7,9] имеют значение true, а выражения D in [E..N ] и 5 in [7,9,11] имеют значение false.
При осуществлении операций над множествами, так же как и при выполнении арифметических и логических операций над обычными переменными, соблюдается определенный приоритет.
Наибольшим приоритетом обладает операция *.
Следующими по приоритету являются операции + и -.
Наименьший приоритет имеют операции in, =, < >, <, <=, >, >=.
При необходимости изменить порядок выполнения операций над множествами, как и для обычных переменных, используют круглые скобки. Значение выражения, заключенного в скобки вычисляется в первую очередь.
|
|
|
