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

 

Над множествами можно производить следующие операции:

1. Определение принадлежности элемента множеству.

2. Сравнение множеств.

3. Действия над множествами.

Рассмотрим подробнее эти операции.

1. Принадлежность множеству

В языке Паскаль обеспечен механизм для определения принадлежности некоторого значения множеству его элементов. Этот механизм реализуется в рамках создания булевского выражения с использованием оператора IN. Структура применения этого оператора имеет вид:

В результате работы этого оператора получается булевское выражение. Например, выражения WED in WEEKDAYS, SAT in WEEKEND являются истинными булевскими выражениями, а выражения SAT in WEEKDAYS, MON in WEEKEND являются ложными.

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

ПРИМЕР 1. Пусть переменная DAY принимает значения всех дней недели. Тогда можно написать программу печати, где этот день недели является рабочим или днем отдыха:

for DAY:= SUN to SAT do

if DAY in WEEKDAY

then WRITELN('Сегодня рабочий день')

else WRITELN('Сегодня день отдыха').

Заметим, что здесь перед циклом нужно определить переменную DAY как переменную перечислимого типа:

var DAY: DAYSOFWEEK.

Итак, мы видим, что на базе перечислимого типа DAYSOFWEEK можно сформировать переменную DAY и множества WEEKDAYS и WEEKEND.

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

НАПРИМЕР:

if (DAY in WEEKEND) and (DAY <> SAT) then

writeln('Сегодня - воскресенье').

Множества имеют различные применения в организации программ.

Одним из них является упрощение написания оператора IF.

Рассмотрим два примера:

1) if (T=0) or (T=32) or (T=212) or (T=276) then...

2) if T in [0, 32, 212, 276] then...

Эти операторы эквивалентны, но второй значительно проще.

Использование множеств позволяет улучшить наглядность и понимание алгоритма работы программы. Например, можно определить, является ли литерная переменная, именуемая ONE_CHAR, цифрой, записав: if ONE_CHAR in ['0'..'9'] then...

Действия над множествами

В Паскале, как и в математике, над множествами можно выполнять следующие логические операции:

а) объединение;

б) пересечение;

в) разность.

Рассмотрим эти операции подробно, но предварительно произведем описание:

type COUNTRIES = (ENG, FR, USA, SP, IT);

var MAP1, MAP2: COUNTRIES.

а) ОБЪЕДИНЕНИЕ (+):

[ENG, FR] + [IT]-> [ENG, FR, IT];

б) ПЕРЕСЕЧЕНИЕ (*):

[ENG, FR, USA] * [ENG, USA, IT] -> [ENG, USA];

в) РАЗНОСТЬ (-):

[ENG..IT] - [ENG..SP] -> [IT].

Эти три операции используются для построения выражений над множествами.

НАПРИМЕР: MAP1:= [FR]; MAP1:= MAP1 + [USA]; MAP2:= MAP1;

MAP1:= MAP1 * (MAP2 + [IT]).

ПРИМЕР 2. РЕШЕТО ЭРАТОСФЕНА. Найти простые числа, не превосходящие заданного.

Алгоритм базируется на вычеркивании чисел, кратных выбранному:

program ERATOS;

const MAXPRIM = 15;

var PRIMES: set of 2..MAXPRIM;

COUNT, MULTIPLE: integer;

begin

¦ writeln('простые числа, меньше ', MAXPRIM);

¦ PRIMES:= [2..MAXPRIM];

¦ for COUNT:= 2 to MAXPRIM do

¦ if COUNT in PRIMES then

¦ begin

¦ ¦ writeln(COUNT);

¦ ¦ for MULTIPLE:=1 to (MAXPRIM div COUNT) do

¦ ¦ PRIMES:= PRIMES-[COUNT*MULTIPLE]

¦ end;

end.

ПОЯСНЕНИЕ. Начинаем с набора множества, состоящего из всех целых чисел в интервале 2..15. Программа при помощи цикла FOR проверяет каждое целое число, входящее в множество. Если целое число является элементом множества, то оно печатается, и из множества удаляются все целые числа, кратные данному числу.

Сравнение множеств

Операция IN весьма полезна, и она позволяет, например, выяснить, являются ли два множества равными. Например, если мы хотим узнать, равны ли множества MAP1 и MAP2, то можно написать:

EGALE:= true;

for MEMBER:= ENG to IT DO

if (MEMBER in MAP1) <> (MEMBER in MAP2) then EGALE:= false.

Это громоздко, поэтому в Паскале есть булевские выражения с применением операций сравнения: =, <>, >=, <=.

НАПРИМЕР: MAP1 = MAP2;

MAP1 <> MAP2;

MAP1 - MAP2 <> [FR];

MAP1 + MAP2 <> [ENG..IT];

MAP1 >= MAP2 (eсли выражение истинно, то MAP2 есть подмножество MAP1).

Печать множеств

 

При работе с множествами немаловажным является вопрос распечатки элементов множества. Отметим, что в большинстве версий языка в операторах WRITE нельзя называть переменные типа "множество". Например, нельзя распечатать множество таким образом:

VAR A: SET OF 1..9;

WRITE(A).

Здесь нет ничего удивительного, т.к. даже если А есть массив, то его тоже нельзя распечатать сразу с помощью одного оператора WRITE(А). Для вывода элементов массива организуются циклы.

Для печати элементов множества также нужно организовать цикл (однократный), внутрь которого вводится некоторая переменная, пробегающая все возможные значения этого множества, а перед оператором WRITE в рамках конструкции IF проверяется, входит ли этот элемент в конкретное множество:

if K in SET1 then write(K).

Как правило, для целей распечатки элементов множеств организуются свои процедуры. Пусть мы имеем дело с множествами, состоящими из целых чисел в границах NIZ и VERH. Зададим множественный тип TS для этих границ:

type INT = NIZ..VERH; TS = set оf INT.

Тогда можно написать процедуру, содержащую в качестве параметра множество:

procedure PRINTSET (OS: TS);

var M: INT;

begin

¦ for M:= NIZ to VERH do

¦ if M in OS then writeln(M);

end.

Теперь можно обращаться к этой процедуре для печати множеств, если только они состоят из элементов, не выходящих из интервала NIZ..VERH. Пусть в разделе констант было описано:

const NIZ = 0; VERH = 10;

тогда можно распечатать множества, обратившись к процедуре:

а) PRINTSET ([5,6,7]); б) PRINTSET ([2]); в) PRINTSET ([3..8]).

Обращение к процедуре можно организовать также в виде:

var SET1, SET2: TS;

SET1:= [..... ]; SET2:= [......]

PRINTSET (SET1); PRINTSET (SET1+SET2); и т.д.

ПРИМЕР 3. В заключение рассмотрим пример целиком, где продемонстрируем все те действия, которые определены над множествами:

program IGRA;

type KOST = 1..6; BROSOK = set of KOST;

var A,B,C: BROSOK;

procedure SRAWNENIE (D: BROSOK);

var K: KOST;

begin

¦ for K:= 1 to 6 do

¦ if K in D then write(K:4); writeln;

end;

begin

¦ A:= [1,3,4]; B:= [2,4,6]; C:= A + B;

¦ write('[1,3,4] + [2,4,6] ='); SRAWNENIE (C);

¦ C:= A - B;

¦ write('[1,3,4] - [2,4,6] ='); SRAWNENIE (C);

¦ C:= A * B;

¦ write('[1,3,4] * [2,4,6] ='); SRAWNENIE (C);

end.

ПОЯСНЕНИЕ. В программе определяются множества A, B, C типа BROSOK, элементами которых являются целые числа из диапазона [1..6], и процедура вывода на печать элементов таких множеств.

ЗАМЕЧАНИЕ 1. Если множество задано перечислимым типом, то его элементы напечатать нельзя. На печать можно вывести элементы только ординального типа: INTEGER, CHAR, BOOLEAN, интервальный.

ЗАМЕЧАНИЕ 2. Один и тот же набор данных можно организовать в виде линейного массива ARRAY, в виде множества SET и в виде строки типа STRING. Какой из этих видов предпочтительнее? Если над элементами (числами) производятся действия, то лучше ARRAY. Если же стоит задача о взаимосвязи элементов нескольких множеств или вопрос о вхождении каких-то объектов в множество, то лучше SET.