Тема № 8 використання множин

Теоретичні відомості

 

Множинні типи даних (множини) являють собою обмежений набір різних елементів базового типу. Кількість елементів, що входять у множину, може змінюватися в межах від 0 до 256 (множина, що не містить елементів, називається порожньою). Множини об'являються в такий спосіб: var Ім'я_множини: set of Тип_компонент;

Операції, що застосовуються до множин такі:

· перевірка на еквівалентність (повертає TRUE, якщо обидві множини еквівалентні): Ім'я_множини_1=Ім'я_множини_2;

· перевірка на нерівність: Ім'я_множини_1<>Ім'я_множини_2;

· перевірка на підмножину (повертає TRUE, якщо перша множина включена в другу): Ім'я_множини_1<=Ім'я_множини_2;

· перевірка входження елемента в множину:

Елемент in Ім'я_множини;

· об'єднання множин (елементи першої множини, доповнені відсутніми елементами з другої множини):

Ім'я_множини_1 + Ім'я_множини_2;

· різниця множин (результат містить елементи з першої множини, що не належать другій): Ім'я_множини_1 - ім'я_множини_2;

· перетинання множин; результат містить елементи, спільні для обох множин: Ім'я_множини_1*Ім'я_множини_2;

Для завдання множини використовується так званий конструктор множини: список специфікацій елементів множини, що відокремлюються один від одного комами; список обрамляється квадратними дужками (наприклад, s1:=[ ] - порожня множина, s2:=[3..9,12] - множина складається з чисел від 3 до 9, та числа 12). Специфікаціями елементів можуть бути константи або вирази базового типу, а також інтервальний тип того ж базового типу.

Зауваження: Елементи множини зберігаються у пам’яті неявно, тобто до окремого елементу множини можливості звернутися не існує. Тому процедури введення та виведення не можуть в якості параметрів використовувати множину чи окремі її елементи. У Прикладі демонструється прийом, як за допомогою циклу та операції in реалізувати “виведення елементів множини на екран” (тобто, псевдовиведення, виводяться значення, що співпадають з елементами множини). Цілком зрозуміло, що у множині не може зберігатися два елементи з одним і тим значенням.

Приклад

Сформувати дві кінцеві множини, заповнивши їх довільними латинськими літерами від A до Z. Обміняти місцями обидві множини, не вводячи додаткової змінної множинного типу.

1) Відомі значення елементів двох кінцевих символьних множин.

2) Ми не маємо додаткової інформації про множини, у завданні не оговорюється чи повинні множини мати пусте перетинання. Для розробки алгоритму розв’язання задачі (враховуючи обмеження на введення додаткової змінної множинного типу) корисними будуть круги Ейлера, за їх допомогою простіше визначити формули перетворень над множинами.

Розглянемо два варіанти можливих вхідних даних:

Перший варіант - множини не перетинаються.

Ми автоматично попадаємо в умови відомої задачі з теорії алгоритмізації та програмування, коли необхідно обміняти місцями значення двох змінних величин, не користуючись третьою. Якщо маємо множини a та b, треба скористатися трьома такими формулами перетворень:

a:= a+b b:= a-b a:= a-b

Другий варіант - множини перетинаються.

Коли множини перетинаються, формули перетворення мають такий вигляд:

a:=a+b-a*b b:=((a+b)-a)+(a-b) a:=((a+b)-a)+(a-b)

Зрозуміло, що другий варіант є більш складним, але й більш загальним, він включає в себе перший (більш обмежений). Тому при розв’язанні будемо використовувати формули, наведені у другому варіанті.

3) Алгоритм:

 

4) Типи даних обираємо такі: litera - символьний; a, b - множини символів.

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

Program p8;

var a,b: set of char;

litera:char;

Begin

a:=[‘F’,’I’,’R’,’S’,’T’]);

b:=[‘S’,’E’,’C’,’O’,’N’,’D’];

a:=a+b-a*b;

b:=((a+b)-a)+(a-b);

a:=((a+b)-a)+(a-b);

write(‘set a = ’);

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