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

Элементы множества заключаются в […].

Множество может не содержать ни одного элемента. В этом случае оно называется пустым [ ].

Если множества используются в программе, то они должны быть описаны либо с помощью раздела Type, либо непосредственно в разделе переменных.

Type имя_типа = set of t;

 базовый тип элементов множества (любой простой кроме real и integer)

Var имя_множества: имя_типа;

Дело вот в чём. Размерность множества, то есть допустимое количество элементов множества обычно небольшое. Для большинства компьютеров оно не превышает 256 (то есть от 0 до 255). Поэтому объявление

Set of Integer является недопустимым.

Вместе с тем запись Type M = Set of Boolean является корректной, поскольку объявляется множество, содержащее два элемента со значениями True и False.

Таким образом, указанным ограничениям на тип элемента удовлетворяют базовые стандартные типы:

Byte,

Char,

перечислимые типы,

ограниченные типы.

Пример. Type Letters = Set of ‘A’..’Z’;

Holidays = Set of 1..31;

U = Set of Char;

I = Set of Byte;

Пример. Type M = Set of (A, B, C, D);

Var G, F: M;

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

G := [A, B, D];

F := [C, A, B];

Пример. Type Town = (Moscow, Kiev, Yalta);

M = Set of Town;

Var P1, P2 : M;

P3 : Set of ‘A’..’Z’;

P4, P5 : Set of 0..9;

Переменная Р1 множественного типа М может принимать следующие значения:

[Moscow] [Kiev] [Moscow, Yalta] [Moscow, Kiev] [Kiev, Yalta] [Moscow, Kiev, Yalta] [Yalta]

В общем случае, если базовое множество содержит N элементов, производный множественный тип определяет 2^N подмножеств. Смотрите пример: 3 элемента, значит, 2³ = 8 подмножеств.

Другой пример описания:

Type MNOG = Set of 1980..2000;

Var M1, M2: MNOG;

В программе элементами множеств М1 и М2 могут быть любые целые числа от 1980 до 2000, например:

M1:= [1988, 1995, 1981];

M2:= [1980, 1981, 1982, 1983];

Приведём примеры описания множеств непосредственно в разделе переменных:

Var M1, M2: Set of 1980..2000;

Var MS: Set of Char;

Здесь элементами являются символьные константы, например:

MS:= [‘A’, ‘N’, ‘R’];

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

6.1. Свойства множеств

1. Все элементы базового типа, образующие множество, должны быть различны. Запись элементов множества (2, 2, 3, 4) некорректна, поскольку два элемента тождественны.

2. Порядок расположения элементов во множестве не фиксируется, то есть множества представляют собой неупорядоченные совокупности объектов (элементов). Множества (1, 3, 5, 6), (6, 1, 3, 5) и (5, 3, 1,6) одинаковы.

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

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

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

1. + объединение множеств;

2. * пересечение множеств;

3. – вычитание множеств;

4. =, < > проверка множеств на равенство, неравенство; множество А равно множеству В, если каждый элемент множества А является элементом множества В и наоборот, каждый элемент множества В является элементом множества А; иначе множества А и В неравны друг другу; результат операции будет логического типа: True или False;

5. <= проверка множества на включение; множество А включено в множество В, если элементы множества А являются также элементами множества В; результат операции А <= В – логический: True или False;

6. IN проверка на принадлежность какого-либо значения множеству; результат операции – логический: True или False; операция S IN A служит для проверки, принадлежит ли элемент базового типа S множеству А.

Пример. Решето Эратосфена. Составить программу, реализующую алгоритм определения набора простых чисел, не превышающих некоторого заданного числа, то есть алгоритм построения “решета Эратосфена”.

Program Resheto;

const N = 256; {Верхняя граница значений элементов множества}

var S: Set of 2..N;

C, M, P: integer;

begin writeln(‘Введите границу’);

read(P);

writeln(‘Простые числа до ‘, P: 3);

S := [2..N];

For C := 2 to P do

If C in S then

begin writeln(C: 3);

for M := 1 to (P div C) do

S := S – [C * M];

end;

end.

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

Пусть Y1, Y2, Y3 и Y4 – заданные множества символьного типа. Они получают значения с помощью операторов присваивания;

Y1 := [‘B’, ‘E’, ‘A’, ‘N’] – боб,

Y2 := [‘S’, ‘P’, ‘O’, ‘O’, ‘N’] – ложка,

Y3 := [‘C’, ‘A’, ‘T’] – кот,

Y4 := [‘C’, ‘O’, ‘L’, ‘D’] – холод,

[‘A’,’N’,’T’] – муравей.

Применяя соответствующие операции над множествами, формируем новое множество:

X := (Y1 * Y2) + Y3 – Y4;

Program A28A;

Var Y1, Y2, Y3, Y4, X: Set of Char; (* множества *)

S: Char; (* символ *)

Begin

Y1 := [‘B’, ‘E’, ‘A’, ‘N’]; {боб}

Y2 := [‘S’, ‘P’, ‘O’, ‘O’, ‘N’]; {ложка}

Y3 := [‘C’, ‘A’, ‘T’]; {кот}

Y4 := [‘C’, ‘O’, ‘L’, ‘D’]; {холод}

X := (Y1 * Y2) + Y3 – Y4;

write(‘X=’);

for S := ‘A’ to ‘Z’ do

if S in X then write(S);

writeln;

if Y3 <= X

then write(‘Yes’)

else write(‘No’);

end.

Здесь для вывода значений нового множества Х используется оператор цикла For. Параметром цикла является символьная переменная S, которая принимает значение каждого символа латинского алфавита от ‘A’ до ‘Z’. Если значение переменной S принадлежит множеству Х, то оно выводится на экран дисплея.

Для решения второй части задачи “Состоит ли муравей из кота?” используется операция включения <= в условном операторе.

Пример. Из множества целых чисел [2..20] выделить следующие множества:

• делящихся на 6 без остатка:

• делящихся без остатка на 2, или на 3 или на 2 и 3;

Введём обозначения:

N2 – множество чисел, делящихся на 2;

N3 – множество чисел, делящихся на 3;

N6 – множество чисел, делящихся на 6;

N23 – множество чисел, делящихся на 2 и 3;

Program A23;

Const N = 20; (* размерность множества*)

Var N2, N3, N6, N23: Set of Integer;

K: Integer;

Begin

N2 := [ ]; (* начальное значение N2 *)

N3 := [ ]; (* начальное значение N3 *)

For K := 1 to N do

Begin

If K mod 2 = 0 then N2 := N2 + [K];

If K mod 3 = 0 then N3 := N3 + [K];

End;

N6 := N2 * N3;

N23 := N2 + N3;

writeln (‘ on 6 devite: ‘);

For K := 1 to N do

If K in N6 then write(K: 3);

writeln;

writeln(‘ on 2 or 3 devite: ‘);

For K := 1 to N do

If K in N23 then write(K: 3);

End.

На экране:

on 6 devite:

6 12 18

on 2 or 3 devite:

2 3 4 6 8 9 10 12 14 15 16 18 20

Пример. Составить программу, реализующую алгоритм построения множеств из символов, проверки вхождения произвольного символа в построенные множества, сравнения двух множеств.

Program Mnogestvo;

Type M = Set of ‘A’..’Z’;

Var M1, M2: M;

B: Char;

Begin M1 := [ ];

M2 := [ ];

Repeat writeln(‘введите символ-элемент 1-го множества‘);

read(B);

M1 := M1 + [B];

Until B =’.’;

Repeat writeln(‘введите символ-элемент 2-го множества‘);

read(B);

M2 := M2 + [B];

Until B =’.’;

writeln(‘ все встретившиеся буквы: ‘);

for B := ‘A’ to ‘Z’ do

if B in M1 + M2 then write(B: 2);

writeln(‘ общие буквы: ‘);

for B := ‘A’ to ‘Z’ do

if B in M1 * M2 then write(B: 2);

if M1 = M2 then writeln(‘ множества совпадают ‘);

if M1 < > M2 then writeln(‘ множества не совпадают ‘);

if M1 >= M2 then writeln(‘ 2-ое есть подмножество 1-го ‘);

if M1 <= M2 then writeln(‘ 1-ое есть подмножество 2-го ‘);

End.

7. КОМБИНИРОВАННЫЕ ТИПЫ

7.1. Описание записей и действия с ними

Для работы с группой данных различного типа введено понятие записи.

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

Примеры записей:

1. Данные о студенте:

Фамилия – массив символов,

Имя – массив символов,

Год рождения – целое число,

Название института – массив символов.

1. Формуляр книги в библиотеке:

Автор – массив символов,

Название – массив символов,

Год издания – целое число,

Издательство – массив символов,

Количество страниц – целое число,

Цена – действительное число.

Все данные можно объединить в одну группу и считать записью. Запись в целом и отдельные её элементы обозначаются именами.

К каждому элементу записи можно обратиться с помощью уточнённого имени. Оно содержит имя записи, а через точку – имя элемента.

Запись, как и другие данные, объявляется в разделе описаний и используется в разделе операторов.

Описание записи имеет следующий вид:

Type имя_типа = Record

Имя_элемента 1: тип;

Имя_элемента 2: тип;

…………

Имя_элемента n-1: тип;

Имя_элемента n: тип;

End;

Var имя_записи: имя_типа;

Здесь служебное слово Record (запись) выполняет роль открывающей операторной скобки, End – закрывающей операторной скобки. Внутри операторных скобок описываются элементы записи. Допускается вместо имени записи указывать список имён, то есть имена записей, разделённые запятыми.

Элементы записи вместе с их описанием называются полями записи.

Пример.

Список 1 Список 2

N^o Фамилия Оценки 1 ------------

1 ------------ (4 штучки 2 ------------

2 ------------ у каждого) 3 ------------

3 ------------ ………… 4 ------------

Type T = Record

N: Integer:

Name: Array [1..10] of Char;

Ball: Array [1..4] of Integer;

End;

Var C1, C2: T;

Здесь сначала введён тип записи Т, а затем в разделе переменных указано, что переменные С1 и С2 имеют тип Т.

Каждый элемент записи имеет своё описание:

N – переменная целого типа,

Name – массив из 10 символов (если фамилия содержит меньше 10 букв, то оставшиеся позиции заполняются пробелами),

Ball – массив из 4-х целых чисел (4 оценки за экзамен).

Допускается описание записи непосредственно в разделе переменных:

Var имя_записи: Record

Имя_элемента 1: тип;

Имя_элемента 2: тип;

…………

Имя_элемента n-1: тип;

Имя_элемента n: тип;

End;

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

а) ввести значения порядковых номеров

Read(C1.N);

Read(C2.N);

б) вычислить сумму первых двух оценок

Summa1 := C1.Ball[1] + C1.Ball[2];

Summa2 := C2.Ball[1] + C2.Ball[2];

Обращение к записи в целом, а не только к отдельным её элементам, допускается лишь в операторе присваивания. Слева и справа от знака присваивания при этом должны использоваться имена записей одинакового типа.

7.2. Оператор присоединения.

Мы отметили, что обращение к элементам записи происходит с помощью уточнённого имени. Оператор присоединения позволяет упростить обращение к элементу записи. Имя записи выносится в заголовок оператора присоединения, а в блоке Begin – end используются только имена элементов записи.

Оператор присоединения имеет вид:

With имя_записи do

Begin

Операторы

End;