Множества
Описание типа «множество»
Множество — это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа «множество» — набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на языке Pascal значения элементов множества указываются в квадратных скобках: [1,2,3,4], ['a','b','c'], ['a'..'z']. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов множества называется его мощностью.
Для описания множественного типа используется словосочетание set of (множество из...). Синтаксическая диаграмма множественных типов имеет следующий вид:
Исходя из синтаксической диаграммы, представим формат записи множественных типов:
type
<имя типа> = set of <элемент_1.....элемент_n>;
var
<идентификатор_1,...> : <имя типа>;
Можно задать множественный тип и без предварительного описания:
var
<идентификатор_1,...> : set of <элемент_1,...>;
Пример:
type
Simply = set of 'a'.. 'h";
Number = set of 1..31;
var
Pr : Simply; N : Number;
Letter : set of char; {Определение множества
без предварительного описания в разделе типов}
В данном примере переменная Рг может принимать в качестве значений символы латинского алфавита от 'а' до 'h'; N — любое значение в диапазоне 1..31; Letter — любой символ. Попытка присвоить другие значения вызовет программное прерывание. Количество элементов множества не должно превышать 256, соответственно номера значений базового типа должны находиться в диапазоне 0..255. Контроль диапазонов осуществляется включением директивы {$R+}. Объем памяти, занимаемый одним элементом множества, составляет 1 бит. Объем памяти для переменной типа «множество» вычисляется по формуле:
Объем памяти = (Max DIV 8) - (Min DIV 8) + 1,
где Мах и Min — верхняя и нижняя границы базового типа.
Операции над множествами
Операция «равно» (=). Два множества А и В считаются равными, если они состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3,4] | [1,2,3,4] | A = B | True |
[‘a’,’b’,’c’] | [‘c’,’a’] | A = B | False |
[‘a’..’z’] | [‘z’..’a’] | A = B | True |
Операция «не равно» (<>). Два множества А и В считаются неравными, если они отличаются по мощности или по значению хотя бы одного элемента.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3] | [3,1,2,4] | A <> B | True |
[‘a’..’z’] | [‘b’..’z’] | A <> B | True |
[‘c’..’t’] | [‘t’..’c’] | A <> B | False |
Операция «больше или равно» (>=). Эта операция используется для определения принадлежности множеств. Результат операции А >= В равен True, если все элементы множества В содержатся в множестве А. В противном случае результат равен False.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3,4] | [2,3,4] | А >= В | True |
[‘a’..’z’] | [‘b’..’t’] | А >= В | True |
[‘z’,’x’,’c’] | [‘c’,’x’] | А >= В | True |
Операция «меньше или равно» (<=). Эта операция используется аналогично предыдущей операции, но результат выражения А <= В равен True, если все элементы множества А содержатся в множестве В. В противном случае результат равен False.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3] | [1,2,3,4] | А <= В | True |
[‘d’..’h’] | [‘z’..’a’] | А <= В | True |
[‘a’,’v’] | [‘a’,’n’,’v’] | А <= В | True |
Операция in. Эта операция используется для проверки принадлежности какого-либо значения указанному множеству. Обычно применяется в условных операторах.
Например:
Значение А | Выражение | Результат |
2 | if А in [1,2,3] then... | True |
‘v’ | if A in ['a'..'n'] then... | False |
X1 | if A in [XO, XI, X2, X3] then... | True |
При использовании операции in проверяемое на принадлежность значение и множество в квадратных скобках не обязательно предварительно описывать в разделе описаний. Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций.
Например, выражение if (a=l) or (a=2) or (a=3) or (a=4) or (a=5) or (a=6) then... можно заменить более коротким выражением if a in [1..6] then... .
Часто операцию in пытаются записать с отрицанием: X NOT in M. Такая запись является ошибочной, так как две операции следуют подряд; правильная инструкция имеет вид NOT (X in M).
Объединение множеств (+). Объединением двух множеств является третье множество, содержащее элементы обоих множеств.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3] | [1,4,5] | А + В | [1,2,3,4,5] |
[‘A’..’D’] | [‘E’..’Z’] | А + В | [‘A’..’Z’] |
[ ] | [ ] | А + В | [ ] |
Пересечение множеств (*). Пересечением двух множеств является третье множество, которое содержит элементы, входящие одновременно в оба множества.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3] | [1,4,2,5] | А * В | [1,2] |
[‘A’..’Z’] | [‘B’..’R’] | А * В | [‘B’..’R’] |
[ ] | [ ] | А * В | [ ] |
Разность множеств (-). Разностью двух множеств является третье множество, которое содержит элементы первого множества, не входящие во второе множество.
Например:
Значение А | Значение В | Выражение | Результат |
[1,2,3,4] | [3,4,1] | А - В | [2] |
[‘A’..’D’] | [‘D’..’Z’] | А - В | [‘A’..’C’] |
[ X1,X2,X3,X4] | [X4,X1 ] | А - В | [X2,X3] |
Результат операций над двумя множествами можно наглядно представить с помощью закрашенных частей двух прямоугольников:
Использование в программе данных типа set дает ряд преимуществ:
· значительно упрощаются сложные операторы if;
· увеличивается степень наглядности программы и понимания алгоритма решения задачи;
· экономятся память, время компиляции и выполнения.
Имеются и отрицательные моменты, основной из них — отсутствие в языке Pascal средств ввода-вывода элементов множества, поэтому программист сам должен писать соответствующие процедуры.
Пример 1
Иллюстрацией описания множеств и операций над ними может служить программа Dem_Mno, в которой описаны множества чисел D, D1, D2, D3. Затем они заполнены следующим образом: множество D1 — четными числами 2, 4, 6, 8; множество D2 — числами 0, 1,2, 3, 5; множество D3 — нечетными числами 1, 3, 5, 7, 9. После этого над множествами выполнены операции объединения, разности и пересечения.
program Dem_Mno; {Демонстрация операций над множествами}
type Digits = set of 0..9:
var
Dl, D2, D3, D : Digits;
begin
Dl:=[2,4.6,8]; {Заполнение множеств}
D2:=[0..3,5];
D3:=[l,3,5,7,9];
D:=D1 + D2; {Объединение множеств Dl и D2}
D:=D + D3; {Объединение множеств D и D3}
D:=D - D2; {Разность множеств D и D2}
D:=D * Dl; {Пересечение множеств D и Dl}
end.
Как видно из текста программы, сначала описан тип Digits = set of 0..9, затем описаны переменные Dl, D2, D3, D этого типа. В первой части программы осуществляется заполнение множеств, а затем над множествами выполняются операции объединения, пересечения, разности.
Так как в Pascal отсутствуют средства ввода-вывода элементов множества, то работу программы придется проверять, выполняя ее в пошаговом режиме и отслеживая изменения значений переменных Dl, D2, D3, D в окне просмотра.
Пример 2
Опишите множество М (1..50). Сделайте его пустым. Вводя целые числа с клавиатуры, заполните множество 10 элементами.
В разделе описания переменных опишем множество целых чисел от 1 до 50, переменную X целого типа будем использовать для считывания числа-кандидата в множество, целую переменную I используем для подсчета количества введенных чисел.
В начале программы применим операцию инициализации множества М:= [], так как оно не имеет элементов и является пустым.
Заполнение множества элементами произведем с использованием оператора for, параметр которого I будет указывать порядковый номер вводимого элемента. Операцию заполнения множества запишем в виде оператора присваивания М:=М+[Х]. Контроль заполнения множества запишем с использованием операции проверки принадлежности in. Если условие X in M выполняется, выведем сообщение о том, что число X помещено в множество. Текст программы описания и заполнения множества будет таким:
program Inpu_Mno;
var
М : set of 1..50;
X. I : integer;
begin
M;= []; {M - пустое множество}
for I:= 1 to 10 do
begin
Write ('Введите ', I, ' - й элемент множества: ');
Readin(X);
if (X in M) then {Если введенное число
входит в множество М}
begin
Writeln(X, ' помещен в множество 1..50');
М:= М+[Х];
end;
end;
Writeln;
end.
Пример 3
Описать множества гласных и согласных букв русского алфавита, определить количество гласных и согласных букв в предложении, введенном с клавиатуры.
Зададим тип Letters — множество букв русского алфавита, затем опишем переменные этого типа: Glasn — множество гласных букв, Sogl — множество согласных букв. Вводимое с клавиатуры предложение опишем переменной Text типа string. Для указания символа в строке Text применим переменную I типа byte. Для подсчета количества гласных и согласных букв опишем переменные G и S. Блок описания программы будет выглядеть следующим образом:
В начале программы поместим заполнение множеств гласных и согласных букв:
После этого реализуем вывод приглашения на ввод предложения и считывание этого предложения в переменную Text.
Перед началом подсчета количества гласных и согласных букв в предложении обнулим значения переменных G и S.
Проверку принадлежности символов, составляющих предложение, множествам гласных или согласных букв русского алфавита реализуем с использованием оператора for, параметр I которого, изменяясь от 1 до значения длины предложения, будет указывать порядковый номер символа в предложении. Принадлежность очередного символа предложения множеству гласных или согласных букв запишем в виде операции in. Если условие Text[I] in Glasn выполняется, то счетчик гласных букв G увеличивается на 1. Если выполняется условие Text[I] in Sogl, тогда увеличивается на 1 счетчик согласных букв S. Если не выполняется ни первое, ни второе условие, значит, очередной символ в предложении не является буквой русского алфавита.
В заключительной части программы поместим вывод сообщения о результатах подсчета гласных и согласных букв в предложении.
program Glasn_Sogl; {Подсчет гласных и согласных букв
в предложении}
type
Letters = set of 'A'..'я';
var
Giasn, Sogl : Letters;
Text : string;
I : byte;
G. S : byte;
begin
Glasn := ['.A', 'a', 'E', 'e', 'И', 'и', 'О', 'о', 'У’, у', 'Э’, ’э’, ‘Ю’, ‘ю’, ‘Я’, ‘я’];
Sоgl := ['Б'.. 'Д', 'б' ..'д’, 'Ж', 'ж', '3', 'з',
'К'..’Н', 'к'..'н', 'П'..'Т’, 'п'..'т', 'Ф’. .' Щ',
' ф'..' щ', ' Ъ', ' ъ', ' Ь', ' ь' ];
Write('Введите предложение ');
Readln(Text);
G:=0;
S:=0;
for I:=1 to Length(Text) do
begin
if Text[I] in Glasn
then G:=G+1;
if Text[I] in Sogl
then S:=S+1
end;
Writeln('В предложении “ ', Text, ' “ ' ,G, ' гласных и ', S, ' согласных букв');
end.
