1. Объединение
Математика:
Pascal:
Объединением двух множеств называется множество элементов принадлежащих обоим множествам.
Пример: ['A', 'B'] + ['C', 'D'] = ['A', 'B', 'C', 'D']
B
A
2. Пересечение
Математика:
Pascal:
Пересечением двух данных множеств называется множество элементов принадлежащих одновременно и первому и второму множеству, общие элементы.
Пример: ['A', 'B']*['C', 'D'] = [];
A
C
B
3. Исключение
Математика:
Pascal:
Вычитанием двух множеств называется множество, состоящее из тех элементов первого множества, которые не являются элементами второго множества.
Пример: ['A', 'B'] – ['C', 'D'] = ['A', 'B'];
A
B
Над значениями множественного типа определены и некоторые операции отношения. Операндами операций над множественными значениями в общем случае являются множественные выражения. Среди операций отношения над значениями множественного типа особое место занимает специальная операция проверки вхождения элемента во множества, обозначаемая служебным словом in. В отличие от остальных операций отношения, в которых значения обоих операндов относятся к одному и тому же множественному типу значений, в операции in первый операнд должен принадлежать базовому типу, а второй – множественному типу значений, построенному на основе этого базового типа. Результатом операции отношения, как обычно, является логическое значение (true или false).
‘a’ in glasn значение операции true;
‘o’ in soglasn значение операции false;
Операция сравнения на равенство множественных типов Паскаля. Множества считаются равными (эквивалентными), если все элементы одного множества присутствуют в другом и наоборот. Для операции сравнения на равенство или неравенство используются символы ‘=’ и ‘<>’.
A:= [2,1,3];
D:= [1,3,2];
Тогда операция A=D имеет значение true, а операция A<>D имеет значение false.
Проверка включения. Одно множество считается включенным в другое (одно множество является подмножеством другого), если все его элементы содержатся во втором множестве. Обратное утверждение может быть и несправедливым. Операции проверки включения обозначаются ‘<=’ и ‘>=’.
letter >= glasn;
soglan <= letter;
Для добавления множеству нового элемента в Паскаль есть операция Include:
Include(<множество>, <элемент>)
Для удаления из множества какого-либо элемента можно воспользоваться операцией Exclude:
Exclude(<множество>, <элемент>)
Необходимо помнить, что добавляемый/удаляемый элемент должен быть тождественного множеству типа.
Все значения множества представляются в памяти последовательностями битов одинаковой длины. За каждое значение базового типа "отвечает" один бит. Если множество содержит некоторый элемент, в "ответственном" за него бите хранится 1, если не содержит - хранится 0.
Внутреннее представление X
x:=[]; 000000000000000>
x:=[2,3,5]; 011010000000000>
x:=[1..15]; 111111111111111>
Операции над множествами сводятся к поразрядным логическим операциям над последовательностями битов, пример, объединение множеств выполняется путем поразрядного логического сложения битов:
x:=[2,3,5]; 011010000000000>
y:=[3,5,7,8]; 001010110000000>
z:=x+y; 011010110000000>
Поразрядные документы входят в набор команд процессора ЭВМ, поэтому выполняется быстро.
Средства работы с множествами позволяют в некоторых случаях сократить программы и сделать их более наглядными и эффективными за счет уменьшения числа проверок.
Примеры
Пример 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.
Пример 2. Дана строка. Сохранить в ней только первые вхождения символов, удалив все остальные.
program ex_set_3;
var m : set of char;
s : string; i : byte;
begin
write('Введите строку: ');
readln(s);
m :=[];
i := 1;
while i <= length(s) do
if s[i] in m then delete(s, i, 1)
else begin m:=m+[s[i]]; i := i + 1 end;
writeln(‘результат: ’,s)
end.
Пример 3.Дан текст на русском языке. Найти количество согласных букв в последнем слове.
while s[i]<>' ' do begin if s[i] in sogl then k:=k+1; i:=i-1;end;
writeln(k);
end.
Пример 4. В городе имеется n высших учебных заведений, которые производят закупку компьютерной техники. Есть шесть компьютерных фирм: «Диалог», «Avicom», «Нэта», «Сервер», «Декада», «Dega.ru». Ответить на следующие вопросы:
1) в каких фирмах закупка производилась каждым из вузов?
2) в каких фирмах закупка производилась хотя бы одним из вузов?
3) в каких фирмах ни один из вузов не закупал компьютеры?
Решим задачу с использованием множеств. Для удобства дальнейших манипуляций в порядке следования занумеруем компьютерные фирмы, начиная с единицы. Занесём информации о месте закупок компьютеров каждым из вузов в отдельное множество.
Ответ на первый вопрос можно получить, выполнив пересечение всех таких множеств.
Ответ на второй вопрос – результат объединения множеств.
И, наконец, на последний – разность множества всех фирм и множества фирм, где хотя бы один вуз делал покупки.
writeln('Каждый из вузов закупил компьютеры в фирмах: '); Print(c);
Rez2(a, n, c);
writeln('Хотя бы один из вузов закупил компьютеры в фирмах: '); Print(c);
writeln('Ни один из вузов не закупил компьютеры в фирмах: '); Print([1..6]-c);
end.
Пример 5. Из множества целых чисел 1..20 выделить: множество чисел, делящихся без остатка на 6; множество чисел, делящихся без остатка или на 2, или на 3.
program mnog2;
const n=20;
var n2,n3,n6,n23: SET OF 1..N;
k:1..N;
begin
n2:=[ ]; n3:=[ ];
for k:=2 to n do
begin
if (k mod 2)=0 then n2:=n2+[k];
if (k mod 3)=0 then n3:=n3+[k];
end;
n6:=n2*n3;
n23:=n2+n3;
writeln('на 6 делятся числа:');
for k:=1 to n do
if k in n6 then write(k:3);
writeln;
writeln('на 2 или на 3 делятся числа:');
for k:=1 to n do
if k in n23 then write(k:3);
writeln
end.
Пример 6.Разгадывание ребусов.
+ МУХА
МУХА
СЛОН
Каждая буква - это цифра, разным буквам соответствуют разные цифры. Необходимо заменить буквы цифрами так, чтобы получилось верное равенство. Найти все решения. Для решения этой задачи используется метод перебора с возвратом. Используем множество S1 для хранения цифр слова МУХА, причем будем вносить в него цифры последовательно, учитывая уже внесенные цифры. Начальное значение S1 - пустое множество. после выбора всех цифр первого слова создаем его числовой эквивалент и числовой образ слова СЛОН. Выделяем цифры СЛОНа (множество S2)и если слова состоят из разных цифр (то есть пересечение S1 и S2 пустое) и все цифры СЛОНа разные (то есть пересечение множеств цифр тоже пустое), то выводим решение на экран. Если же нет, то идет возврат - удаляем из множества S1 последнюю внесенную цифру и пытаемся выбрать еще одно значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.
Заметим, что значение буквы М в слове МУХА может иметь значения от 1 до 4, а буква А в этом же слове не может быть равна 0.
Program Rebus;
Type
MN = set of 0..9;
Var
m, u, h, a : 0..9;
n1, n2 : Integer;
s, l, o, n : 0..9;
S1, S2 : MN;
Procedure Print(x, y : Integer);
Begin
writeln(x:5);
writeln('+');
writeln(x:5);
writeln(' ');
writeln(y:5);
End;
Begin
S1 := [ ];
S2 := [ ];
for m := 1 to 4 do
begin
S1 := S1+[m];
for u := 0 to 9 do
if Not(u in S1)
then
begin
S1 := S1+[u];
for h := 0 to 9 do
if Not (h in S1)
then
begin
S1 := S1+[h];
for a := 1 to 9 do
if Not (a in S1)
then
begin
S1 := S1+[a];
n1 := 1000*m+100*u+10*h+a;
n2 := 2*n1;
s := n2 div 1000;
l :=n2 div 100 mod 10;
o := n2 div 10 mod 10;
n := n2 mod 10;
S2 := [s, l, o, n];
if (S1*S2=[ ]) and ([s]*[l]*[o]*[n]=[ ])
then
Print (n1, n2);
S1 := S1-[a];
end;
S1 := S1-[h];
end;
S1 := S1-[u];
end;
S1 := S1-[m];
end;
End.
Контрольные вопросы
1. Что понимают под множеством в Pascal?
2. Что такое базовый тип множества?
3. Как задаются постоянные множества (множества-константы) в Pascal?
4. Напишите все способы описания множеств в Pascal?
5. Возможен ли прямой доступ к элементам множества?
6. Перечислите операции над множествами.
7. Что называется объединением множеств. Приведите пример.
8. Что называется пересечением множеств. Приведите пример.
9. Что называется исключением множеств. Приведите пример.
10. Перечислите операции отношения допустимые над множествами. Охарактеризуйте их.
11. С помощью какой операции поверяют вхождение элемента во множество?
12. Как значения множества представляются в памяти?
13. К чему сводятся операции над множествами?
14. Какая операция предназначена для добавления множеству нового элемента? Ее синтаксис.
15. Какая операция предназначена для удаления из множества нового элемента? Ее синтаксис.
Содержание отчета:
1. Лабораторная работа № 4
2. Тема лабораторной работы.
3. Цель работы.
4. Краткие теоретические сведения (в виде ответов на контрольные вопросы).
Pascal: 
Объединением двух множеств называется множество элементов принадлежащих обоим множествам.
Пример: ['A', 'B'] + ['C', 'D'] = ['A', 'B', 'C', 'D']
Pascal: 
Пересечением двух данных множеств называется множество элементов принадлежащих одновременно и первому и второму множеству, общие элементы.
Пример: ['A', 'B']*['C', 'D'] = [];
Pascal: 
Вычитанием двух множеств называется множество, состоящее из тех элементов первого множества, которые не являются элементами второго множества.
Пример: ['A', 'B'] – ['C', 'D'] = ['A', 'B'];