Множина – це структурований тип даних, що являє собою
наб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.
Операції з
множинами
Результатом виразів з множинами є
значення True або False, в залежності від істинності виразу.
Операція: =. Дві множини A і B рівні, якщо воні складаються з одних і тих самих
елементів. Порядок слідування елементів значення немає.
Приклад:
 Операція: <>. Дві множини A і B вважаються не рівними, якщо воні відрізняються хоча б одним
елеементом.
Операція: >=. Результат A>=B рівний True, якщо всi елементи
множини B мiстяться в A.
Операцiя: <=. Виконується аналогічно >=.
Операцiя: IN. Перевiряє належність деякого
заданого значення вказанiй множині. В цій бінарній операції перший елемент –
вираз, а другий – множина одного і того ж типу. Повертає True, якщо вираз має
значення, що належить множині. Використовується, як правило, в умовних
операторах.
Приклад:
Об'єднанням множин: +. Об'єдннанням двох множин є множина, яка
містить елементи обох множин.
Приклад:
Значення
А Значення В Вираз
Результат
[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 елементів.
|