Множества

Множеством в Паскале называется набор значений какого-нибудь порядкового типа, подчиняющийся специфическим правилам, о которых мы поговорим дальше. В программе множество записывается в виде списка этих значений в квадратных скобках. Например, [7,5,0,4] или [‘п’, ’ж’, ’л’]. Множество не должно состоять более, чем из 256 элементов и не должно содержать элементов с порядковыми номерами меньше 0 и больше 255.

Если в множестве элемент повторяется, то считается, что он входит туда только один раз. Например, множества [2,5,2] и [2,5] эквивалентны.

Порядок элементов в множестве не играет роли. Множества [2,5] и [5,2] эквивалентны.

В описании тип множества задается словами set of. Например, конструкция

VAR a: set of Byte

говорит о том, что задана переменная, значением которой может быть любое множество из любого числа элементов типа Byte. Так, в некоторый момент процесса выполнения программы значением a может быть множество [210, 3, 92], а через пару секунд - [8, 5, 3, 26, 17].

Конструкция VAR c: set of (april, may, june) говорит о том, что переменная cможет иметь значением любое множество из имен april, may, june. Например, [april, june].

Конструкция VAR d: set of 10..18 говорит о том, что переменная dможет иметь значением любое множество целых чисел из диапазона от 10 до 18.

Над множествами определено несколько операций. Рассмотрим три из них: объединение (+), пересечение (*) и разность (-).

Операция [1,2]*[3,4] будет иметь результатом [ ], то есть пустое множество.

Вот операции сравнения множеств:

Операция проверки вхождения элемента E в множество a:

if E in a then...

Например, a:= [1,2,4]; if 2 ina then... {Если 2 входит в множество a....}

К сожалению, Паскаль не желает выводить множества на печать, точно так же, как он не желает печатать перечислимые типы. Поэтому просто так узнать, из каких элементов состоит множество, не удастся. Вот один из обходных путей:

Пусть задано множество a, описанное, как set of Byte. Будем пробовать уменьшать его на все элементы подряд, от 1 до 255, и каждый раз, когда это удается, распечатывать соответствующее число. Вот подходящий фрагмент, в котором мне понадобится “для транзита” еще одно множество b:

for i:=1 to 255 do begin
b:=a-[i];
if a<>b then begin WriteLn(i); a:=b end
end {for}

Вот гораздо более короткий и естественный путь:

for i:=0 to 255 do if i in a then WriteLn(i)

Я думаю, что работа с множествами Паскаля - любопытное и полезное занятие. Например, она нужна математикам, чтобы проверять свои теоремы. Я проиллюстрирую работу с множествами на простеньком примере:

Медиум загадывает шестерку чисел, каждое в диапазоне от 0 до 10 (числа могут и совпадать). Экстрасенс отгадывает их, называя свою шестерку. Есть ли между шестерками совпадающие числа? Если есть, то распечатать их.

Сначала решим задачу традиционными методами, а именно с применением массивов, а не множеств:

CONST razmer = 10; kol = 6;

VAR Medium, Extrasens: array [1..kol] of 0..razmer;
i, j, k:Integer;
BEGIN
{ Формируем случайным образом две шестерки: }
Randomize;

for i:= 1 to kol do begin
Medium[i]:=Random(razmer+1);
Extrasens[i]:=Random(razmer+1)

end {for};
{ Проверяем две шестерки на совпадение: }
k:=0; {Нам придется подсчитывать количество совпадений. k - счетчик}
for i:= 1 to kol do
for j:= 1 to kol do
if Medium[i] = Extrasens[j] then begin
k:=k+1;
WriteLn(Medium[i]) {Распечатываем совпадения}
end {if};
if k=0 then WriteLn(‘Не угадал ни разу‘)
END.

У данной программы есть недостатки. Пусть медиум загадал числа 2 4 1 5 4 8, а экстрасенс назвал 1 4 9 6 1 4. Программа распечатает числа 4 4 1 1 4 4, а достаточно было бы только 1 4. К тому же пришлось организовывать счетчик совпадающих чисел, чтобы иметь возможность ответить, угадано ли хоть одно число.

А теперь применяем множества:

CONST razmer = 10; kol = 6;

VAR Medium, Extrasens, a: set of 0..razmer;
i:Integer;
BEGIN
{ Формируем случайным образом две шестерки: }

Randomize;
Medium:=[ ]; Extrasens:=[ ]; {Начинаем формировать “с нуля”, то есть с пустых множеств}
for i:= 1 to kol do begin
Medium:= Medium + [Random(razmer+1)]; {Наращиваем по одному элементу в множестве медиума}
Extrasens:= Extrasens + [Random(razmer+1)] {Наращиваем по одному элементу в множестве экстрасенса}
end {for}

a:= Medium * Extrasens; {Множество a содержит совпадающие числа. Вот так – одним махом.}
if a=[ ] then WriteLn(‘Не угадал ни разу‘)
else begin
WriteLn(‘Есть совпадения, вот они: ‘);
{ Распечатываем элементы множества a: }
for i:=0 to razmer do if i in a then WriteLn(i);

end {else}
END.

Задание 118: Случайным образом формируется небольшое множество заглавных букв русского алфавита. Определить, входит ли в это множество хотя бы одна из букв М,И,Ф.