ОБЩАЯ ФОРМА ЗАПИСИ:
TYPE <имя типа>: SET OF <тип компонент>;
VAR <имя переменной>: <имя типа>;
или
VAR <имя переменной>: SET OF <тип компонент>;
ПРИМЕРЫ: var LETTERS: set of 'A'..'Z';
DAYS: set of 1..31; MNOGCHAR: set of char.
Итак, мы увидели, что в описании типа множество есть общее с описанием типа массив, но есть и существенные отличия:
а) нет типа индекса (элементы множества не индексируются);
б) есть, как в массиве, тип компонент.
НАПРИМЕР:
type DAYSOFWEEK = (SUN, MON, TUE, WED, THU, FRI, SAT);
var WEEKDAYS, WEEKEND: set of DAYSOFWEEK.
Теперь этим описанным переменным можно присваивать различные значения, которые суть множества, состоящие из элементов перечислимого типа - названий дней недели:
a) WEEKDAYS:= [MON, TUE, WED, THU, FRI];
б) WEEKEND:= [SAT, SUN],
причем в случае а) можно поступить иначе: WEEKDAYS:= [MON..FRI].
Заметим также, что указанные множества из элементов перечислимого типа нельзя сформировать с помощью оператора READ (в силу специфики этого типа).
Аналогом нуля в типе множество есть пустое множество: [].
Над множествами можно производить следующие операции:
1. Определение принадлежности элемента множеству.
2. Сравнение множеств.
3. Действия над множествами.
Рассмотрим подробнее эти операции.
Принадлежность множеству
В языке Паскаль обеспечен механизм для определения принадлежности некоторого значения множеству его элементов. Этот механизм реализуется в рамках создания булевского выражения с использованием оператора 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;
¦ for M:= NIZ to VERH do
¦ if M in OS then writeln(M);
Теперь можно обращаться к этой процедуре для печати множеств, если только они состоят из элементов, не выходящих из интервала 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;
¦ for K:= 1 to 6 do
¦ if K in D then write(K:4); writeln;
end;
¦ 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);
ПОЯСНЕНИЕ. В программе определяются множества A, B, C типа BROSOK, элементами которых являются целые числа из диапазона [1..6], и процедура вывода на печать элементов таких множеств.
ЗАМЕЧАНИЕ 1. Если множество задано перечислимым типом, то его элементы напечатать нельзя. На печать можно вывести элементы только ординального типа: INTEGER, CHAR, BOOLEAN, интервальный.
ЗАМЕЧАНИЕ 2. Один и тот же набор данных можно организовать в виде линейного массива ARRAY, в виде множества SET и в виде строки типа STRING. Какой из этих видов предпочтительнее? Если над элементами (числами) производятся действия, то лучше ARRAY. Если же стоит задача о взаимосвязи элементов нескольких множеств или вопрос о вхождении каких-то объектов в множество, то лучше SET.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39