Множини

Множина – це структурований тип даних, що являє собою набip взаємо - пов'язаних за якоюсь ознакою або групою ознак об'ектiв, якi можна розглядати як єдине цiле. Кожний член множини називається елементом множини. Всi елементи множини повиннi належати одному з скалярних типiв, за виключенням дiйсного. Цей тип називаеться базовим типом множини. Базовим типом може бути довільний перелічувальний тип, окрім Word, Integer, LongInt.

Область значень типу множина – набiр всiх можливих пiдмножин, які складаються з елементiв базового типа.

На Паскалi значення елементiв множини вказується в квадратних дужках: [1, 2, 3, 4], ['а', 'b', 'c'], ['a'..'z']. Якщо множина не має елементiв, вона називається пустою i позначаеться як [ ]. Опис типу множини:

Type < iм'я типу > = Set of < базовий тип >;

Var < iдентифікатор,... >: < iм'я типу >;

Намагання присвоїти iншi значення множинi (що не вiдповiдають базовому типу) викликає переривання роботи програми.

Приклад:

Type Proste = Set of (3, 5, 7, 11, 13);

Nomer = Set of 1..31;

Symbol = Set of Char;

Var Pr: Proste; N: Nomer; SM: Symbol;

Bukva: Set of (‘a’, ‘e’, ‘i’, ‘j’);

Begin

Pr:=[3]; Bukva:=[a, j]; SM:=[‘A’..’Z’];

Кількість елементів множини не повинна перевищувати 256, тому номери значень базового типу знаходяться в діапазоні 0..255.

6.2.1.1. Операції з множинами

Результатом виразів з множинами є значення True або False, в залежності від істинності виразу.

Операція: =. Дві множини A і B рівні, якщо воні складаються з одних і тих самих елементів. Порядок слідування елементів значення немає.

Приклад:

А	B	Результат
[1,2,3,4] [‘a’,’b’,’c’] [‘a’,..,’z’]	[1,4,3,2] [‘c’,’a’] [‘z’,..,’a’]	A=B True A=B False A=B True

Операція: <>. Дві множини A і B вважаються не рівними, якщо воні відрізняються хоча б одним елеементом.

Операція: >=. Результат A>=B рівний True, якщо всi елементи множини B мiстяться в A.

Операцiя: <=. Виконується аналогічно >=.

Операцiя: IN. Перевiряє належність деякого заданого значення вказанiй множині. В цій бінарній операції перший елемент – вираз, а другий – множина одного і того ж типу. Повертає True, якщо вираз має значення, що належить множині. Використовується, як правило, в умовних операторах.

Приклад:

Значення A	Вираз	Результат
'v'	if A in [1,2,3] then if A in ['а'..'n'] then if A in [10..20] then	True Fаlse Fаlse

Об'єднанням множин: +. Об'єдннанням двох множин є множина, яка містить елементи обох множин.

Приклад:

Значення А Значення В Вираз Результат

[1, 2, 3] [1, 4, 5] A + B [1, 2, 3, 4, 5]

Пересiчення множин: *. Пересiчення двох множин є третя множина, яка містить елементи, що входять одночасно в обидвi множини.

Приклад:

Значення А Значення В Вираз Результат

[1, 2, 3] [1, 4, 2, 5] А * В [1, 2]

Рiзниця множин: –. Різницею двох множин є третя множина, яка мiстить елементи першої множини, що не входять в другу.

Приклад:

Значення А Значення В Вираз Результат

[1, 2, 3, 4] [3, 4, 1] А - В [2]

Операцiя::=. Присвоєння значення множині. Приклад: A:=A+[5];

В доповнення до цих операцій можна використовувати дві процедури:

Include(S, I) – включає новий елемент до множини. Тут S – множина, що складається з елементів базового типу TSetBase; I – елемент TSetBase, який необхідно включити до множини.

Exclude(S, I) – виключає елемент І з множини S.

Розглянемо приклад програми, що реалізує алгоритм виділення з першої сотні натуральних чисел всіх простих чисел (таких, що діляться без остачі лише на самих себе і 1). В основі цього алгоритма лежить прийом, який відомий, як “решето Ератосфена”. У відповідності з цим алгоритмом спочатку формується множина BeginSet, яка складається з усіх цілих чисел в діапазоні від 2 до N. В множину PrimerSet (вона буде містити прості числа) вміщується 1. Потім циклічно повторюються такі дії:

· взяти з BeginSet число Next, яке входить в нього першим і помістити його в PrimerSet;

· вилучити з BeginSet число Next і всі інші числа, кратні йому, тобто 2* Next, 3* Next і т.д.

Цикл повторюється до тих пір, поки множина BeginSet не стане пустою. Цю програму не можна використовувати для довільного N, оскільки в довільній множині не може бути більше 256 елементів.

Program SampleNumber;

Const N = 255;

Type SetOfNumber = Set of 1..N;

Var

N1, Next, i: Word;

BeginSet, PrimerSet: SetOfNumber;

S: String;

Begin

BeginSet:=[2..N]; { Створюємо початкову множину }

PrimerSet:=[1]; { Створюємо перше просте число }

Next:=2; { Наступне просте число }

While BeginSet<>[ ] do begin

N1:=Next;

While N1<=N do begin

Exclude(BeginSet, N1); { Вилучення кратного з множини }

N1:=N1+Next; { Наступне кратне }

End;

Include(PrimerSet, Next); { Включення простого числа в множину}

Repeat

Inc(Next); { Пошук наступного простого числа }

Until (Next in BeginSet) or (Next > N)

End;

S:=’1’;

For i:=2 to N do

If i in PrimerSet then S:=S+’,’+Str(i);

Writeln(‘Список чисел: ‘, S);

End.

Приклад:

Виконати операцію об’єднання над заданими множинами a i b:

Текст програми

Program suma;

Type

p=1..100;

M=set of p;

Var

A,B,C:M;

x:p;

Begin

A:=[1,2,3];

B:=[2,4,6,8];

C:=A+B;

Writeln('Об’єднання множин');

write('C=');

for x:=1 to 100 do

if x in C then

write (x);

writeln;

end.

Результат виконання програми

Об’єднання множин

С=123468