Написание программы на языке Паскаль с использованием множеств

Цель работы: формирование знаний и умений по работе с множествами. Приобретение навыков обработки множеств.

Краткие теоретические сведения

Основные понятия и определения

Множество – это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект во множестве называется элементом множества.

Все элементы множества должны принадлежать одному из скалярных типов, кромевещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа множество – набор всевозможных подмножеств, составленных из элементов базового типа.

В выражениях на языке Паскаль значения элементов множества указываются в квадратных скобках:[1,2,3,4], [‘a’,’b’,’c’], [‘a’..’z’]. Если множество не имеет элементов, оно называется пустым и обозначается, как [ ]. Количество элементов множества называется его мощностью.

Формат записи множественных типов:

Type

<имя типа> = set of <элемент 1,…., элементN>;

Var

<идентификатор, ….>: <имя типа>;

Можно задать множественный тип и без предварительного описания:

Var

<идентификатор, …>: set of <элемент1, …>;

Пример:

Type

Simply = set of ‘a’..’h’;

Number = set of 1..31;

Var

Pr: Simply;

N: Number;

Letter: set of char; {определение множества без предварительного описания в разделе типов}

В данном примере переменная Pr может принимать значения символов латинского алфавита от ‘a’ до ‘h’; N – любое значение в диапазоне 1..31; Letter – любой символ. Попытка присвоить другие значения вызовет программное прерывание.

Количество элементов множества не должно превышать 256, соответственно номера значений базового типа должны находиться в диапазоне 0..255. Контроль диапазонов осуществляется включением директивы {$R+}. Объем памяти, занимаемый одним элементом множества, составляет 1 бит.

Объем памяти для переменной типа множество вычисляется по формуле:

Объем памяти = (Max DIV 8) – (Min DIV 8) + 1,

где Max и Min – верхняя и нижняя границы базового типа.

Операции над множествами

При работе с множествами допускается использование операций отношения “=”, “<>”, “>=”, “<=”, объединения, пересечения, разности множеств и операции in. Результатом выражения с применением этих операций является значение True или False.

Операция “равно” (=). Два множества А и В считаются равными, если состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘a’, ’b’, ’c’] [‘a’..’z’]	[1,2,3,4] [‘c’, ‘a’] [‘z’..’a’]	A=B A=B A=B	True False True

Операция “не равно” (<>). Два множества А и В считаются не равными, если они отличаются по мощности или по значению хотя бы одного элемента.

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘a’..’z’] [‘c’..’t’]	[3,1,2,4] [‘b’.. ‘z’] [‘t’..’c’]	A<>B A<>B A<>B	True True False

Операция “больше или равно” (>=). Операция “больше или равно” (>=) используется для определения принадлежности множеств. Результат операции А >=В равен True, если все элементы множества В содержаться в множестве А. В противном случае результат равен False.

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘a’..’z’] [‘z’,’x’,’c’]	[2,3,4] [‘b’.. ‘t’] [‘c’,’x’]	A>=B A>=B A>=B	True True True

 

Операция “меньше или равно” (<=). Эта операция используется аналогично предыдущей операции, но результат выражения А<=В равен True, если все элементы множества А содержаться во множестве В. В противном случае результат равен False.

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘d’..’h’] [‘a’,’v’]	[1,2,3,4] [‘z’.. ‘a’] [‘a’,’n’,’v’]	A<=B A<=B A<=B	True True True

Операция in. Операция in используется для проверки принадлежности какого-либо значения указанному множеству. Обычно применяется в условных операторах.

Значение А	Значение В		Результат
‘v’ X1	if A in [1,2,3] then.. if A in [‘a’..’n’] then.. if A in [X0,X1,X2,X3] then..		True True True

При использовании операции in проверяемое на принадлежность значение и множество в квадратных скобках не обязательно предварительно описывать в разделе описаний. Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций. Например, выражение if(a=1) 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] [‘A’..’D’] []	[1,4,5] [‘E’.. ‘Z’] []	A+B A+B A+B	[1,2,3,4,5] [‘A’..’Z’] []

Пересечение множеств (*). Пересечением двух множеств является третье множество, которое содержит элементы, входящие одновременно в оба множества.

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘A’..’Z’] []	[1,4,2,5] [‘B’.. ‘R’] []	A*B A*B A*B	[1,2] [‘B’..’R’] []

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

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘A’..’Z’] [X1,X2,X3,X4]]	[3,4,1] [‘D’.. ‘Z’] [X4,X1]	A-B A-B A-B	[2] [‘A’..’C’] [X2,X3]

Результат операций рад двумя множествами можно наглядно представить с помощью закрашенных частей двух кружочков:

Объединение Пересечение Разность

Использование в программе данных типа set дает ряд преимуществ: значительно упрощаются сложные операторы if, увеличивается степень наглядности программы и понимания алгоритма решения задачи, экономятся память, время компиляции и выполнения.

Имеются и отрицательные моменты, основной из них – отсутствие в языке Паскаль средств ввода-вывода элементов множества, поэтому программист сам должен писать соответствующие процедуры.

Иллюстрацией описания и операций над множествами может служить следующий фрагмент программы:

Program Dem_Mno; {демонстрация операций над множествами}

Type

Digits= set of 0..9;

Var

D1, D2, D3, D:Digits;

Begin

D1:=[2,4,6,8]; {заполнение множеств}

D2:=[0..3,5];

D3:=[1,3,5,7,9];

D:=D1+D2; {объединение множеств D1 и D2}

D:=D+D3; {объединение множеств D и D3 }

D:=D-D2; {разность множеств D и D2 }

D:=D*D1; {пересечение множеств D и D1}

end.

Как видно из текста программы, сначала описан тип Digits=set of 0..9, затем описаны переменные D1,D2,D3,D этого типа. В первой части программы осуществляется заполнение множеств, а затем над множествами выполняются операции объединения, пересечения, разности.

 

Вторым примером работы с множествами может служить следующая задача: описать множество М (1..50) и сделать его пустым. Вводя целые числа с клавиатуры, заполнить множество 10 элементами.

Program Input_Mno;

Var

M: set of 1..50;

X,I:integer;

Begin

M:= [ ]; {М – пустое множество}

for I:=1 to 10 do

Begin

write(‘введите ‘, I, ‘ –й элемент множества: ‘);

readln (X);

if (X in M) then {если введенное число входит в множество М}

Begin

writeln(X,’ помещен в множество 1..50’);

M:=M+[X];

end;

end;

writeln;

End.

В разделе описания переменных описано множество целых чисел от 1 до 50, переменная Х целого типа, которая используется для считывания числа-кандидата в множество, и целая переменная I, используемая для подсчета количества введенных чисел. В начале программы применена операция инициализации множества М, так как оно не имеет элементов и является пустым:

M:= [ ];

Заполнение множества элементами производится с использованием оператора повтора for, параметр которого I будет указывать порядковый номер вводимого элемента. Операция заполнения множества записывается оператором присваивания:

M:=M+[X];

Контроль заполнения множества записан операцией проверки принадлежности in. Если условие X in M выполняется, выводится сообщение о том, что число Х помещено в множество.

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

Зададим тип Letters –множество букв русского языка, затем опишем переменные этого типа: Glasn-множество гласных букв, Sogl-множество согласных букв. Вводимое с клавиатуры предложение опишем переменной Text типа String. Для указания символа в строке Text применим переменную I типа Byte.Для подсчета количества гласных и согласных букв опишем переменные Gи S. Проверку принадлежности символов, составляющих предложение множествам гласных или согласных букв русского языка запишем с использованием цикла for, параметр I которого, изменяясь от 1 до значения длины предложения, будет указывать порядковый номер символа в предложении. Принадлежность очередного символа предложения множеству гласных или согласных букв запишем операцией in. Если символ является гласной буквой (Text[I] in Glasn), то счетчик гласных букв G увеличивается на 1. Аналогично с согласными буквами. Текст программы может выглядеть так:

Program Glasn_Sogl;

Type

Letters=set of ‘A’..’я’;

Var

Glasn, Sogl:Letters;

Text:String;

I:Byte;

G,S:Byte;

Begin

Glasn:=[‘A’,’a’, ‘Е’,’е’,’И’,’и’,’О’,’о’,’У’,’у’,’Э’,’Ю’,’ю’, ‘Я’,’я’];

Sogl:=[‘Б’..’Д’,’б’..’д’,’Ж’,’ж’,’З’,’з’,’К’..’Н’,’к’..’н’,’П’..’Т’,’п’..’т’,’Ф’..’Щ’,’ ‘ф’..’щ’,’Ъ’,’ъ’,’Ь’,’ь’];

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.

Порядок выполнения работы

1. Изучить теоретические сведения по теме “Работа с множествами”.

2. Получить у преподавателя индивидуальное задание.

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

4. Показать работающую программу преподавателю.

5. Ответить на контрольные вопросы.

Контрольные вопросы

1. Множества. Основные понятия и определения.

2. Операции над множествами.

3. Фрагменты программ с использованием множеств.

 

Лабораторная работа № 28