Л а б о р а т о р н а р о б о т а N 11
Програмування роботи з множинами на мовi Турбо Паскаль
Множини - це набiр елементiв однакового порядкового типу.
На вiдмiну вiд масивiв множини вiдрiзняються
невпорядкованiстю та змiнною кiлькiстю елементiв - вiд нуля
до всiх можливих значень базового типу. Можливими значеннями
змiнних типу "множина" є всi пiдмножини базового типу.
Кiлькiсть елементiв множини може мiнятися вiд 0 до 256.
Множина без елементiв називається пустою. Базовими типами
елементiв множини можуть бути: byte, char, boolean,
перелiковий та дiапазони з них.
Оголошення типу "множина":
type
iм'я_типу = set of базовий_тип;
Приклади оголошень множин елементiв:
type
digit=set of 0..9;
chardigit='0'..'9';
characters=set of char;
setbool=set of boolean;
colors=set of (while, red, green, blue, black);
var
set1:digit;
set2:chardigit;
set3:characters;
set4:setbool;
set5,set6:colors;
Для задання множини елементiв використовуються
конструктори множин: список значень елементiв множини у
квадратних дужках, який задається через кому. Значення
елементiв можуть задаватися константами або виразами базового
типу, а також типом-дiапазоном того ж базового типу. Iнiцiалiзацiя
множин може здiйснюватися при оголошеннi їх як констант,
або присвоєнням значення змiннiй з типом множина в операторнiй
частинi програми. Множини є виключно внутрiшнiм типом Турбо Паскаля,
для якого не допускаються операцiї вводу-виводу з текстових
файлiв, а також вводу з клавiатури, виводу на екран, роздруку на принтер.
Приклад оголошення нетипованих та типованих констант-множин:
Const a=[1,2,3];
b=['a'..'z','0..9'];
Const c:setbool=[true,false];
d:colors=[white,black];
Приклад присвоєння значень змiнним типу множина у програмi:
set1:=[1,3,5];
set2:=['0'..'5','6'];
set3:=[#65..#70];
set4:=[true,false];
set5:=[red,blue,black];
set6:=[];
Порядок слiдування елементiв множини значення не має.
Одинаковi елементи множини можуть повторюватися. Наступнi
зображення позначають одну i ту ж множину:
[1,2,3];
[1,1,2,3];
[1,2,3,2,2,3,1];
Значенням змiнної, оголошеної як множина, можуть бути всi комбiнацiї її елементiв,
включаючи пусту множину. Наприклад, для множини [1,2,3]
такими комбiнацiями є [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [].
Операцiї над множинами
Над множинами допускаються бiнарнi операцiї об'єднання, рiзницi, перетину
та вiдношення. Множини, якi беруть участь в операцiї, повиннi бути
сумiсного типу.
Позначення операцiй об'єднання, рiзницi та перетину приведенi в наступнiй
таблицi.
----------------------------------------------------------------------
Операцiя Дiя Типи операндiв
----------------------------------------------------------------------
+ об'єднання множини з сумiсним порядковим типом
(крiм word, integer, longint, shortint)
- рiзниця -"-
* перетин -"-
-----------------------------------------------------------------------
Операцiї над множинами пiдпорядковуються правилам логiки множин.
1) Операцiя об'єднання множин. Порядкове значення x належить A+B, якщо
x належить A або x належить B. Наприклад, якщо
A:=[0..3,6];
B:=[3..7];
C:=A+B;
то множина C мiститиме елементи вiд 0 до 7, що еквiвалентно наступному
присвоєнню: C:=[0..7] .
2) Операцiя рiзницi множин. Порядкове значення x належить A-B, якщо
x належить A, але x не належить B. Таким чином, результатом операцiї
C:=A-B є множина [0,1,2].
3) Операцiя перетину множин. Порядкове значення x належить A*B,
якщо x одночасно належить множинам A та B. Результатом
присвоєння C:=A*B є множина елементiв [3,6].
Операцiї вiдношення
Над множинами визначенi наступнi операцiї вiдношення:
----------------------------------------------------------------------
Операцiя Дiя Типи операндiв
----------------------------------------------------------------------
= еквiвалентно множини з сумiсним порядковим типом
(крiм word, integer, longint, shortint)
<> не еквiвалентно -"-
<= пiдмножина -"-
>= надмножина -"-
in перевiрка належностi злiва вiд операцiї - елемент множини,
елемента множинi зправа - множина сумiсного типу
----------------------------------------------------------------------
Результатом операцiй вiдношення над множинами є значення констант
булевського типу true або false.
Вираз A=B приймає значення true, якщо множини A та B складаються
з однакових елементiв без врахування їх повторень та порядку слiдування.
Вираз A<=B приймає значення true, якщо кожен елемент множини A є також
елементом множини B.
Вираз A>=B приймає значення true, якщо кожен елемент множини B є також
елементом множини A.
Вираз x in A приймає значення true, якщо значення x елементу порядкового
типу є елементом множини A.
Прiорiтет операцiй над множинами
Послiдовнiсть виконання операцiй над множинами пiдпорядковується
загальним правилам прiорiтету операцiй Турбо Паскаля. Найвищий прiорiтет
має мультиплiкативна операцiя *. Аддитивнi операцiї + та - мають
нижчий прiорiтет вiд *. Найнищий прiорiтет мають операцiї вiдношення.
Включення елемента у множину та його виключення
Для включення елемента у множину використовується операцiя +,
а для виключення операцiя -. Включати або виключати можна тiльки елемент, який має
тип, сумiсний з базовим типом множини.
Включати або виключати можна константу, або змiнну. Для цього
константу або змiнну необхiдно охопити квадратними дужками i використати
потрiбну операцiю, наприклад:
var a:set of byte;
x:byte;
Begin
a:=[];
read(x);
a:=a+[x];
End.
У версiї Турбо Паскаль 7.0 для включення та виключення елемента у множину
використовуються процедури Include та Exlude, якi мають наступнi заголовки:
Procedure Include(var s:SetOfT; Elem:T);
Procedure Exclude(var s:SetOfT; Elem:T);
Процедура Include включає елемент типу T у множину з базовим
типом SetOfT, а процедура Exlude - виключає такий елемент.
Формування множини
Змiнна типу "множина" не може бути введена з клавiатури
або виведена на екран. Але якщо базовий тип множини допускає ввiд з клавiатури
то можна ввести значення змiнної з таким базовим типом, а потiм
включити цю змiнну у множину, охопивши її квадратними дужками та використавши
операцiю об'єднання множин. Якщо базовий тип множини не допускає вводу
з клавiатури (наприклад, булевський та перелiковий типи), то
необхiдно використати явне перетворення базового типу.
Для прикладу розглянемо формування множини перелiкового типу.
Type colors=(red,green,blue);
var S:set of colors;
i:0..2;
Begin
S:=[];
while not EOF do
begin
read(i);
s:=s+[colors(i)];
end;
End.
Вивiд складу множини
Для виводу складу множини необхiдно використати операцiю
перевiрки належностi елемента множинi. Якщо елемент входить у множину i його
базовий тип допускає вивiд, то такий елемент виводиться на екран,
або видруковується. Якщо базовий тип елемента не допускає прямий вивiд, то
необхiдно використати явне перетворення типу.
Наступна програма здiйснює вивiд складу множини.
var a,b,c:set of byte;
i:byte;
Begin
a:=[0..3,6];
b:=[3..7];
c:=a+b;
for i:=0 to 255 do
if i in c then writeln(i);
if c=[] then writeln('Множина пуста')
End.
Розмiщення в оперативнiй пам'ятi
В оперативнiй пам'ятi множина зберiгається як бiтовий масив, де
кожен бiт показує, чи є даний елемент у множинi, чи нi.
Максимальний розмiр множини не перевищує 32 байти.

Порядок роботи
1. По виданому завданню розробити алгоритм та програму розв'язку
задачi.
2. Використовуючи засоби iнтегрованого середовища Турбо Паскаля,
ввести, вiдлагодити та виконати програму.
3. Оформити звiт по роботi по наступнiй схемi:
- назва роботи;
- мета роботи;
- теоретичнi вiдомостi про роботу з множинами у Турбо Паскалi;
- завдання для роботи;
- програма на мовi Турбо Паскаль;
- результати роботи програми;
- висновки

Iндивiдуальнi завдання
1. Оголосiть змiннi так, щоб були правильними наступнi
присвоєння:
colors: = [red, blue];
letters: = ['a'..'z'];
digits: = [5,8..16];
daysworked: = [Monday..Friday];
logic: = [true];
Виведiть значення цих змiнних.
11.3. Оголошенi множини
Var a,b,c: set of 0..9;
з початковою iнiцiалiзацiєю:
a: = [0..3,6];
b: = [3,4,5,6,7];
Виведiть результати наступних операцiй:
a) c: = a+b;
в) c: = a-b;
с) c: = a*b;
3. Оголошенi множини
Var
a,b : set of char;
з початковою iнiцiалiзацiєю:
a: = [ 'a'..'z'];
b: = ['a', 'm', 'x'];
Запрограмуйте та виведiть результати наступних операцiй:
а) a:=b;
б) a>=b;
в) b<=a;
г) b:=['x','a','m'];
д) 'k' in a;
е) 'k' in b;
4. Враховуючи те, що елементи множини не можна безпосередньо вво-
дити або виводити , напишiть програму для роздруку всiх елементiв
множини з базовим типом byte.
5. Враховуючи прiорiтет операцiй над множинами з базовим типом char,
a:=['a'..'z'];
b:=['k'..'r','x'];
c:=['m'];
обчислити та вивести результат виразу:
(a-b*c>=['n']) or ('b' in a)
6. Пiдрахувати та вивести кiлькiсть елементiв множини iз заданим базовим ти-
пом char: x:=['a'..'f','0'..'9'];
7. Написати процедуру, яка друкує в алфавiтному порядку всi еле-
менти множини з типом
type
letters=set of 'a'..'z';
8. Пiдрахувати кiлькiсть символiв рядка
Var s: packed array [1..100] of char;
що входять в множину ['0'..'9', '+','-','*']
10. Заданий рядок символiв:
Var s: string [20]
Визначити кiлькiсть символiв (голосних), що входять в наступну
множину ['a', 'e', 'i', 'o', 'u'].
11. Написати функцiю для пiдрахунку кiлькостi рiзних значимих
цифр в десятковому запису натурального числа n. Цифри iз числа
видiляти справа налiво i записувати їх у множину.
12. Написати процедуру, яка друкує у зростаючому порядку всi циф-
ри, що не входять в десятковий запис натурального числа n. Цифри
iз числа видiляти справа налiво i записувати їх у множину.
13. Використовуючи роботу iз множинами надрукувати всi символи, що
входять у рядок
Var
str: string [20];
бiльше одного разу.
14. Заданi множини елементiв з базовим типом Char:
A={'a','b','c','d'}, B={'b','d','e','f'}.
Вияснити чи є у них спiльнi елементи i вивести їх значення на
друк.
15. Заданi множини елементiв iз базовим типом byte:
A={1,3,5,7,9}, B={3,5,9} .
Вибрати всi елементи множини А, що не належать В i вивести їх
значення на друк.
16. Використовуючи оголошенi типи
type продукт = (хлiб, масло, молоко, м'ясо, риба, сiль, сир,
ковбаса, цукор, чай, кава);
асортимент = set of продукт;
магазини = array [1..20] of асортимент;
Написати процедуру DISPONIBILITE (Магазини, Var A, B, C: асорти-
мент), яка присвоюЇ параметрам A, B, C наступнi значення:
А - множина продуктiв, якi є в усiх магазинах;
В - множина продуктiв, кожен iз яких є хоча б в одному магазинi;
С - множина продуктiв, яких немає нi в одному магазинi.
17. Заданий рядок, що складається iз слiв, роздiлених пропусками.
Використовуючи роботу iз множинами знайти:
а) кiлькiсть голосних букв в кожному словi;
б) слово з мiнiмальною кiлькiстю приголосних букв.
18. Задана множина елементiв з базовим перелiковим типом (людина,
вовк, коза, капуста). Написати програму, що моделює безпечну
переправу у двомiсному човнi через рiчку всiх суб'єктiв множини
(щоб вовк не з'їв козу, а коза не з'їла капусту). Результати
моделювання роздрукувати.