Множини
Paskal дозволяє оперувати трьома множинами, як трьома типами даних. Для визначення типу множина використовується вираз:
Set Of простий тип
1 Наприклад, описання виду:
Type
Char Set = set of ‘A’.. ‘Z’
Визначає тип множина, значеннями якого є множини символів – букв, а елементами множини – символи – латинські букви від А до Z.
2 Описання виду
Type
Number Set = set of 0..50 визначає тип множина, а членами множини – цілі числа, які знаходяться в межах від 0 до 50.
3 Порожня множина є елементом всіх типів множин.
4 Приклади описів типів множина:
Type
Symbol Set = set of ‘ ‘..’ ‘;
Colour = WHITE, BLUE, RED;
Colour Set = set of Colour;
T1 = set of 0..9
Var
C: colour; Col Set: Colour Set;
T: inteper;
TSet: T1
В даному випадку значенням змінної Т може бути будь-яка цифра від 0 до 9, а значенням змінної TSet – довільна сукупність цифр від 0 до9.
5 Над множинами в Р допустимі 4 операції;
§ Oб’єднання "+" Об’єднання множин – це множина, яка містить усі елементи цих множин без повторень.
§ Перетин " " Перетин множин – це множина, яка складається з елементів, які є спільними для всіх множин.
§ Різниця " - " Різницею множин А і В є множина, яка складається з елементів, що є в А, але не є в В.
§ Операція in.
Операція in дозволяє визначити чи належить елемент множині, чи ні. Першим операндом, розміщеним зліва від слова in, є вираз базового типу тобто типу, якому повинні належати всі члени множини. Другий операнд, який знаходиться справа in, повинен мати тип множина.
Наприклад: Red in [RED, WHITE] – результат true
8 in [0..3, 6, 9] – результат false.
7 В Р. програмі множина задається в вигляді списку елементів, заключеного в [ ]. В [ ] може бути 1 або більше елементів, а може не бути жодного порожня множина. В якості елементу може використовуватись const, змінна, вираз, значення якого належить базовому типу, а також парі елементів, розділених двома крапками інтервал значень.
8 В Р. можна використовувати інструкції присвоєння слідуючих виразів:
ColSet: = [WHITE, RED];
ColSet: = [ ];
TSet: = [1, 7, 5];
TSet: = [1..5, 8];
TSet: = [8 mod 4, 15 div 5].
9 При роботі з множинами можна використовувати операція порівняння:
=, , =, =
Операції "=" і " " дозволяють перевірити, рівні дві множини, чи ні. З допомогою oперацій " =" і " =" можна визначити, чи є одна множина підмножинною іншої.
Приклад:
[RED, WHITE] = [ RED, GREEN] – резкльтат false
[RED] = [RED, WHITE] – результат true.
Операції в порядку зменшення пріоритету розміщуються так:
+
In, =, , =, = рівнопріоритетні операції
Приклад №1 Із файла Input вводиться текст, який містить символи від знаку "+" до лівої квадратної дужки " [ ". Роздрукувати символи тексту в порядку коду ASCII з символів, що зустрічаються повторно, виводити тільки один.
Program Sort Input, Output;
Var
S: char;
Sets: set of ‘+’ [‘;
I: ‘+’..’[‘;
Begin
Sets: = [ ];
Read S
While not Eof do begin
While not Eoln do
begin
Sets: = Sets + [S];
Read S
end
Readln
End
For I: = ‘+’ to ‘[‘ do
If I in Sets
Then Write I else; writeln end.
Приклад №2 Написати програму, яка друкує всі прості числа з відрізку 2..N діючи по методу "решета Ератосорена"
"Решето Ератосорена"
Program Rach;
Coust
N = 15
Var
S: set of 2..N
{початкова множина чисел}
i, k: integer;
Begin
S: = [2..N];
for i: = 2 to N do
if i in Sthen begin
writeln i;
{виводимо найменше із елементів S}
{забираємо із S числа, крайні і}
for k: = 1 to N div i do
S: = S – [ki];
end {if }
End.
Внутрішнє представлення множин
Знайомство з внутрішнім представленням множин допоможе нам зрозуміти особливості і обмеження, властиві цьому типові даних.
Всі значення множини представляються в пам’яті послідовностями бітів однакової довжини. За кожне значення базового типу "відповідає" один біт. Якщо множина вміщує деякий елемент, в "відповідальному" за нього біті зберігається 1, якщо не вміщує – зберігається 0.
Приклад.
Var X: set of 1..15;
Внутрішнє представлення Х
X: = [ ]; 000.0.000.0.000.0.000.
011010000000000
X: = [2, 3,5];
X: = [1..15]; 111111111111111
Операції над множинами зводяться до "поразрядныx" логічних операцій над послідовністю бітів, наприклад об’єднання множин використовується шляхом "поразрядного" логічного додавання бітів.
X: = [2, 3, 5]; 011010000000000
Y: = [3, 5, 7, 8]; 0010101.10000000
Z: = X+Y; 01101.0110000000
"Поразрядные" операції входять в набір команд процесора ЕОМ, тому виконуються швидко.
