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

МНОЖЕСТВЕННЫЙ ТИП ДАННЫХ.

Множество – это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа множества – набор всевозможных подмножеств, составленных из элементов базового типа. Таким образом, множество в языке Pascal – это ограниченный упорядоченный набор различных элементов одного (базового) типа. В выражениях на языке Pascal значения элементов множества указываются в квадратных скобках: [1,2,3,4], [‘a’,’b’,’c’],[‘a’..’z’]. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов множества называется его мощностью, которое должно быть не более 256.

Для описания множественного типа используется словосочетание set of (множество из …). Множества, используемые в программе, могут быть описаны либо в разделе описания типов type:

type <имя типа> = set of <тип элементов>;

var <имя множества>: <имя типа>;

либо в разделе описания переменных var:

var <имя множества>: set of <тип множества>;

Например:

type mnog_Ch = set of char;

var mn1: set of char;

mn2:mnog_Ch;

mn3: set of ‘a’..’z’;

s1: set of integer;

s2: set of 1000..1200;

При работе с множествами допускается использование операций отношения («=», «<>», «>=», «<=»), объединения, пересечения, разности множеств и операции in. Результатом выражений с применением этих операций является значение true или false.

Операция «равно» (=). Два множества A и B считаются равными, если они состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.

Значение A	Значение B	Выражение	Результат
[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

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

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

Операция «больше или равно» (>=). Операция «больше или равно» (>=) используется для определения принадлежности множеств. Результат операции A>=B равен true, если все элементы множества B содержатся в множестве A. В противном случае результат равен false.

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

Операция «меньше или равно» (<=). Эта операция используется аналогично предыдущей операции, но результат выражения A<=B равно true, если все элементы множества A содержатся в множестве B. В противном случае результат равен false.

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

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

Значение A	Выражение	Результат
	If A in [1,2,3] then …	True
‘v’	If A in [‘a’..’n’] then …	False
X1	If A in [X0,X1,X3] then …	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).

Объединение множеств (+). Объединение двух множеств является третье множество, содержащее элементы обоих множеств.

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

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

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

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

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

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

Пример 1.

«Мешанина». Если взять то общее, что есть у боба с ложкой, добавить кота и поместить в тепло, то получится муравей. Так ли это? Состоит ли муравей из кота?

Решение:

pogram pr1;

var y1,y2,y3,y4,x: set of char;

s: char;

begin

y1:=[‘б’,’о’,’б’];

y2:=[‘л’,’о’,’ж’,’к’,’а’];

y3:=[‘к’,’о’,’т’];

y4:=[‘т’,’е’,’п’,’л’,’о’];

x:=(y1*y2)+y3-y4;

writeln(‘множество x’);

for s:=’а’ to ‘я’ do

if s in x then writeln(s);

writeln;

if y3<=x then writeln(‘муравей состоит из кота’)

else writeln(‘муравей не состоит из кота’)

end.

Пример 2.

«Решето Эратосфена». Составить программу поиска простых чисел в числовом промежутке [1..n]. Число n вводится с клавиатуры.

Решение:

Простым числом называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом «решета Эратосфена», идея которого заключается в следующем: сформировать множество М, в которое поместить все числа заданного промежутка. Затем последовательно удалить из него элементы, кратные 2, 3, 4 и так далее, до [n/2] (целая часть числа), кроме самих этих чисел. После такого «просеивания» в множестве М останутся только простые числа.

program pr2;

var m: set of byte;

i,k,n:integer;

begin

writeln(‘Ввести размер промежутка (до 255) ‘);

readln(n);

m:=[2..n];

for k:=2 to n div 2 do

for i:=2 to n do

if (i mod k=0) and (i<>k) then m:=m-[i];

for i:=1 to n do

if i in m then writeln(i:3);

readln

end.

Пример 3.

Известен набор продуктов – хлеб, масло, сыр, молоко, имеющиеся в ассортименте магазинов. В три магазина доставлены отдельные виды этих продуктов. Требуется построить множества A, B, C, которые содержат соответственно:

- продукты, имеющиеся одновременно во всех магазинах;

- продукты, имеющиеся, по крайней мере, в одном из магазинов;

- продукты, которых нет ни в одном из магазинов.

Решение:

program amaf;

const n=3;

type prod=(xl,ms,sr,ml);

assort=set of prod;

mag=array[1..n] of assort;

var m1:mag;

x:prod;

a,b,c,xm1:assort;