Міністерство освіти і науки України
НУ „Львівська політехніка”
Кафедра __________
ЗВІТ
Про виконання лабораторної роботи №.....
На тему:________________________________________________________________
________________________________________________________________________
________________________________________________________________________
___________________
(Студент)
___________________
(Група)
___________________
(Керівник лаб. Занятть)
------Львів 200…------
Л а б о р а т о р н а р о б о т а 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 байти.

Завдання для роботи: Написати функцiю для пiдрахунку кiлькостi рiзних значимих цифр в десятковому запису натурального числа n. Цифри iз числа видiляти справа налiво i записувати їх у множину.