Множинні типи Організація множин

Множина - це невпорядкований набір різних об'єктів однакового типу. У мові Паскаль використовують тільки скінченні множини, причому всі елементи множини повинні бути однакового типу, визначеного в Паскалі. Тип елементів множини називається базовим. Як базовий може бути довіль­ний ординальний тип (тобто будь-який простий, за винятком real). Цілого типу застосовують тільки діапазон, для якого за­значають мінімальне і максимальне значення.

Змінні чи сталі множинного типу набувають значення, які є множиною. Для задання множини використовують так званий конструктор множини, який має вигляд списку елементів мно­жини, взятого в квадратні дужки. Елементами множини можуть бути сталі базового типу або вирази цього ж типу. Множина може не мати елементів, тоді вона є порожньою і її описує кон­струкція [].

Приклади задання множин: [4,6,9,12] - множина, елемен­тами якої є цілі числа; ['i', 'm', 'р', 'q', 'r'] - множина, елементами якої є символи; [m, 10] - множина, що містить значення змінної цілого типу т і цілого числа 10.

Якщо елементи множини утворюють діапазон значень базового типу, то їх можна задавати скорочено, як і елементи діапазонного типу. Наприклад, множину [3, 4, 5, 6, 7] можна записати [3..7]. Частину елементів можна перелічувати, а частину - задавати як діапазон: [3, 4, 5..100].

[ n..2*n] - множина цілих чисел від п до виразу 2п.

[пн, вт, чт] - множина елементів деякого перелічуваного типу, який потрібно описати.

Якщо в діапазоні А..С, яким задана множина, А=С, то ця множина містить один елемент, що дорівнює А. Якщо С<А, то множина порожня. Наприклад: [3..1], ['r'..'b'] - порожні множи­ни.

Якщо якийсь елемент повторюється, то вважають, що є тільки один такий елемент. Наприклад: [2, 3, 7, 2, 3] те ж саме, що [2, 3, 7].

З наведених прикладів зрозуміло, що для задания мно­жинного типу треба задати деякий базовий тип. Відповідний множинний тип (змінна) може набувати значень, що є множи­нами, одержаними довільними комбінаціями базового типу.

Загальний вигляд опису множинного типу такий:

type <ім'я_типу>= set of <ординальний_тип>;

Опишемо тип

type

р=1..3;

b=set of p;

var

x:b;

Тоді х може набувати значень, якими є всі множини, що можуть бути складені з цілих чисел 1, 2 і 3. Змінна х може мати такі значення: [ ] - порожня множина, [1], [2], [3], [1,2], [1,3], [2,3] і [1,2,3]. Усі ці множини можуть бути значеннями змінної х множинного типу, заданого як set of p. Інші приклади:

type

day=(pn, vt, sr, ct, pt, sb, nd);

den=set of day;

var

roboch: den;

sezon: set of (lito, osin, zyma, vesna);

logic: set of boolean;

У цьому прикладі тип den описаний явно, як множинний, що має базовим перелічуваний тип day. Решта типів задано неявно в описі змінних sezon і logic. Змінна roboch може набувати значень [], [pn], [vt],..., [pn, vt], [pn, sr],..., [sb, nd], [pn, vt, sr],..., [pn, vt, sr, ct, pt, sb, nd].

Змінна sezon: [ ], [lito],..., [lito, osin, zyma, vesna].

Змінна logic: [ ], [true], [false], [true, false].

Для присвоєння значень змінним множинного типу вико­ристовують оператор присвоєння

v:=s,

де v - змінна множинного типу; s - вираз цього типу. Елементи s належать до того ж базового типу. Як вираз s може бути змінна множинного типу або саме значення - стала множинного типу. Наприклад, для описаних вище змінних правильними є опера­тори присвоєння

roboch:=[vt, ct, pt]; logic:=[true];

Тут як вирази використані сталі.

Операції над множинами

Операції над множинами в мові Паскаль практично збіга­ються з операціями в теорії множин. Це передусім операції об'єднання, перерізу і різниці множин. Нехай А і В - вирази однакового множинного типу, тобто це множини, елементи яких належать до одного і того ж базового типу. Тоді:

об'єднанням А +В множин А і В є множина, елементи якої належать хоча б до однієї множини А чи В. Наприклад, А = [1, З, 6, 7], а В - [2, 4, 6, 7], то А+В дорівнює [1, 2, 3, 4, 6, 7];

перерізом А *В множин А і В є множина, елементи якої одночасно належать до множини А і множини В. Для тих же А і В переріз А *В буде [6, 7];

різницею А-В множин А і В є множина, що складається з елементів множини А, які не належать до множини В. Якщо як множини А і В взяти використані раніше, то А-В дає множину

[1,3].

За допомогою операцій з множинами можна будувати ви­рази множинного типу. Пріоритетність виконання операцій така сама, як і під час обчислення арифметичних виразів: у дужках, '*', '+' і '-'.

Операції відношення

Крім описаних операцій, над множинами виконують ще операції відношення (порівняння). Нехай А і В - множини од­накового множинного типу, х - вираз базового типу, до якого належать елементи А і В. У табл. 8.1 наведені операції відно­шення над множинами і результати, які одержують для відпо­відних значень А і В.

Таблиця 8.1. Операції відношення над множинами.

Остання з наведених у табл. 8.1 операцій відрізняється тим, що перший операнд належить до базового типу, а другий - до множинного, побудованого на основі цього базового.

Зазначимо, що операції порівняння ">" і "<" над операн­дами множинного типу не використовують.

Наведемо приклади використання операцій відношення. Нехай R:=[4, 7, 9,11]. Тоді

5 in R дорівнює false

[7,11]<=R дорівнює true

[4, 7, 8,11]=R дає false

[ ]<=R дає true

Бажано, щоб усі операції з множинами виконувались швид­ко. Тому в більшості трансляторів максимальний розмір мно­жин обмежений розміром слова відповідного комп'ютера. Зок­рема, в Турбо Паскалі допустимий як базовий тип будь-який дискретний (ординальний), кількість елементів якого не перевищує 256, причому значення елементів для цілих типів повинні бути в діапазоні від 0 до 255. Такі вимоги задовольняють тільки типи byte, char, перелічувані типи, а також діапазони (обмежені типи). Тоді кожен елемент множини подають одним розрядом (О означає відсутність, а 1 - наявність елемента в множині).

Як приклад використання змінних множинного типу роз­глянемо такий алгоритм. Треба визначити всі прості числа в діапазоні 2..n, де n>=2, і вивести їх у порядку спадання. Ефек­тивнішим для розв'язування цієї задачі є алгоритм з назвою "решето Ератосфена", оскільки він не використовує так званих довгих операцій - множення і ділення. Суть цього алгоритму така:

1. Помістимо всі числа від 2 до п в "решето".

2. Виберемо з "решета" найменше з чисел, що є в ньому.

3. Помістимо це число серед "простих" чисел.

4. Виберемо з "решета" всі числа, кратні йому.

5. Якщо "решето" не порожнє, то повторити кроки 2-5.

Нехай n=101. Введемо дві множини: Р - множина аналізо­ваних чисел, тобто "решето", і S - множина простих чисел. Початкові значення цих множин такі:

Р=[2, 3, 4..101];

s=[ ]

Візьмемо перше число - 2 і введемо в множину S, одержи­мо 5=[2]. З множини Р заберемо 2 і всі кратні йому. Одержимо Р=[3, 5, 7, 9, 11,..., 101]. Так продовжуємо доти, доки з Р не будуть забрані всі елементи.

Зазначимо, що вилучення з множини Р деякого числа k виконується за допомогою оператора P:=P-[k]. Аналогічно, до­давання числа k до множини 5 виконує оператор S:=S+[k]. Си­туацію, чи "решето" порожнє, перевіряють, задаючи значення відношення Р=[ ]. Якщо це значення дорівнює true, то Р - по­рожня множина.

(Одержання множини простих чисел з діапазону 2..101 з використанням множинного типу}

program PROST (output);

const

N=101;

type

chysla=set of 2..N;

var

P, S: chysla;

r, k:2..101;

begin {ініціалізація}

P:=[2..N];

S:=[]; r:=2;

repeat {відшукання чергового простого числа}

while not (r in P) do

r:=r+1;

{введення простого числа в S}

S:=S+[r];

{вилучення з Р числа r і кратних йому}

k:=r;

repeat

P:=P-[k];

k:=k+r ;

until k>N;

until P=[ ];

{виведення простих чисел у зворотному порядку}

for k:=n downto 2 do

if k in S

then write(k);

writeln

end.