 |
|
Множини. Дії над множинами
Питання для вивчення:
1. Поняття множин.
2. Опис множин.
3. Операції над множинами.
Поняття множин. Множина - це структурований тип даних, який представляє собою набір взаємозалежних за якоюсь ознакою або групі ознак об'єктів, які можна розглядати як єдине ціле. Кожен об'єкт в Множині називається елементом множини. Всі елементи множини повинні належати одному з порядкових типів, що містить не більше 256 значень. Цей тип називається базовим типом множини. Базовий тип задається діапазоном або перерахуванням. Область значень типу Множина - набір всіляких підмножин, складених з елементів базового типу. У виразах на мові Паскаль значення елементів множини вказуються в квадратних дужках: [1,2,3,4], ['а', 'b', 'з'], ['a' .. 'z']. Якщо множина не має елементів, вона називається порожньою і позначається як []. Кількість елементів множини називається її потужністю. Множина може приймати всі значення базового типу. Базовий тип не повинен перевищувати 256 можливих значень. Тому базовим типом множини можуть бути byte, char, boolean і похідні від них типи. Множина в пам'яті зберігається як масив бітів, в якому кожен біт вказує чи є елемент належить оголошеному Множинаі чи ні. Максимальне число елементів множини 256, а дані типу Множина можуть займати не більше 32 байт.
Число байтів, що виділяються для даних типу Множина, обчислюється за формулою:
ByteSize = (max div 8) - (min div 8) + 1,
де max і min - верхня і нижня межі базового типу даної множини.
Номер байта для конкретного елемента Е обчислюється за формулою:
ByteNumber = (E div 8) - (min div 8),
номер біта всередині цього байта за формулою:
BitNumber = E mod 8
Не має значення порядок запису елементів множини всередині конструктора.
Наприклад, [1, 2, 3] та [3, 2, 1] - це еквівалентні множини.
Кожен елемент в Множині враховується тільки один раз. Тому Множина [1,2, 3, 4, 2, 3, 4, 5] еквівалентно [1 .. 5].
Опис множин. Змінні множинного типу описуються так:
Var <ідентифікатор>: set of <базовий тип>;
Наприклад:
Var A, D: Set Of Byte;
B: Set Of 'a' .. 'z';
C: Set Of Boolean;
Не можна вводити значення у множинну змінну процедурою введення і виводити процедурою виведення.
Множинна змінна може отримати конкретне значення тільки в результаті виконання оператора присвоювання:
<Множинна змінна>: = <множинний вираз>;
Наприклад:
A: = [50, 100, 150, 200];
B: = ['m', 'n', 'k']; C: = [True, False];
D: = A;
Крім того, вирази можуть включати в себе операції над множинами.
Операції над множинами. Об'єднанням двох множин A і B називається множина, що складається з елементів, що входять хоча б в одне з множин A чи B. Знак операції об'єднання в Паскалі «+».
Приклади:
1) [1, 2, 3, 4] + [3, 4, 5, 6] => [1, 2, 3, 4, 5, 6]
2) [] + ['a' .. 'z'] + ['A' .. 'E', 'k'] => ['A' .. 'E', 'a' .. 'z' ]
3) [5 <4, true and false] + [true] => [false, true]
Перетином двох множин A і B називається множина, що складається з елементів, одночасно входять в Множина A і в Множина B.
Знак операції перетину в Паскалі «*».
Приклади:
1) [1, 2, 3, 4] * [3, 4, 5, 6] => [3, 4]
2) ['a' .. 'z'] * ['A' .. 'E', 'k'] => ['k']
3) [5 <4, true and false] * [true] => []
Різницею двох множин A і B називається множина, що складається з елементів множини A, що не входять в Множину B.
Приклади:
1a) [1, 2, 3, 4] - [3, 4, 5, 6] => [1, 2]
1b) [3, 4, 5, 6] - [1, 2, 3, 4] => [5, 6]
2a) ['a' .. 'z'] - ['A' .. 'E', 'k'] => ['a' .. 'j', 'i' .. 'z']
2b) ['A' .. 'E', 'k'] - ['a' .. 'z'] => ['A' .. 'E']
3a) [5 <4, true and false] - [true] => [false]
3b) [true] - [5 <4, true and false] => [true]
Операція входження. Це операція, що встановлює зв'язок між множиною і скалярною величиною, тип якої співпадає з базовим типом множини. Якщо x - така скалярна величина, а M - Множина, то операція входження записується так: x in M. Результат - логічна величина true, якщо значення x входить в Множину M, і false - в протилежному випадку.
Наприклад, 4 in [3, 4, 7, 9] - true, 5 in [3, 4, 7, 9] — false.
Використовуючи дану операцію, можна не тільки працювати з елементами множини, але і, навіть якщо в рішенні задачі явно не використовуються Множини, деякі логічні вирази можна записати більш лаконічно.
Натуральне число n є двозначним. Замість виразу (n> = 10) and (n <= 99) можна записати n in [10 .. 99].
Символ c є російською буквою. Замість виразу (c> = 'А') and (c <= 'Я') or (c> = 'а') and (c <= 'п') or (c> = 'р') and (c < = 'я') пишемо c in ['А' .. 'Я', 'а' .. 'П', 'р' .. 'Я'] і т.д.
Додати новий елемент в Множину можна з використанням операції об'єднання. Наприклад, a: = a + [5] Для цих же цілей в Turbo Pascal 7.0 призначена процедура Include: include (M, A) M - Множина, A - змінна того ж типу, що й елементи множини M. Той же приклад можна записати так: Include (a, 5)
Виключити елемент з Множини можна за допомогою операції «різницю множин». Наприклад, a: = a-[5] Для цих же цілей в Turbo Pascal 7.0 призначена процедура Exclude: exclude (M, A) M - Множина, A - змінна того ж типу, що й елементи множини M. Той же приклад можна записати так: Exclude (a, 5).
Завдання 1. У місті є n вищих навчальних закладів, які здійснюють закупівлю комп'ютерної техніки. Є шість комп'ютерних фірм: «Діалог», «Avicom», «Нетан», «Сервер», «Декада», «Dega.ru». Відповісти на наступні питання:
1) у яких фірмах закупівля проводилася кожним з вузів?
2) в яких фірмах закупівля проводилася хоча б одним з вузів?
3) в яких фірмах жоден з вузів не закуповував комп'ютери?
Вирішимо завдання з використанням множин. Для зручності подальших маніпуляцій у порядку проходження пронумеруємо комп'ютерні фірми, починаючи з одиниці. Занесемо інформації про місце закупівель комп'ютерів кожним з вузів в окрему Множину.
Відповідь на перше питання можна отримати, виконавши перетин всіх таких множин.
Відповідь на друге питання - результат об'єднання множин.
І, нарешті, на останнє - різниця Множинаі всіх фірм і Множинаі фірм, де хоча б один вуз робив покупки.
program ex_set_1;
type firma = set of 1 .. 6;
v = array [0 .. 20] of firma;
const f: array [1 .. 6] of string [10] = ('Діалог', 'Avicom', 'Нетан', 'Сервер', 'Декада', 'Dega.ru');
{Процедура введення інформації про закупівлю комп'ютерів в черговий
фірмі}
procedure vvod (var a: firma);
var i: byte; ans: 0 .. 1;
begin
a: = [];
for i: = 1 to 6 do
begin
Write ('Вуз купував комп'ютери в фірмі', f [i], '(1 - так, 0 - ні)?'); ReadLn (ans);
if ans = 1 then a: = a + [i]
end;
end;
{Процедура виведення елементів масиву, номери яких містяться в Множині}
procedure
Print (a: firma);
var i: byte;
begin
for i: = 1 to 6 do if i in a then write (f [i]: 10);
writeln
end;
{Процедура, яка дає відповідь на перше питання}
procedure Rez1 (a: v; n: byte; var b: firma);
var i: byte;
begin
b: = [1 .. 6];
for i: = 0 to n-1 do b: = b * a [i];
end;
{Процедура, яка дає відповідь на друге питання}
procedure Rez2 (a: v; n: byte
firma);
var i: byte;
begin
b:
for i: = 0 to n-1 do b: = b + a [i];
end;
var a: v; n, i: byte; c: firma;
begin
write ('Скільки ВНЗ робили закупівлю?'); readln (n);
for i: = 0 to n-1 do vvod (a [i]);
Rez1 (a, n, c);
writeln ('Кожен з вузів закупив комп'ютери у фірмах:');
Print (c);
Rez2 (a, n, c);
writeln ('Хоча б один з вузів закупив комп'ютери у фірмах:');
Print (c);
writeln ('Жоден з вузів не закупив комп'ютери у фірмах:'); Print ([1 .. 6]-c);
end.
Питання для контролю вивченого матеріалу:
1. Що таке Множина?
2. Чому Множина є структурованим типом даних?
3. Як зберігається Множина в пам'яті ЕОМ? Який максимальний об'єм оперативної пам'яті може бути відведений під зберігання однієї Множини?
4. Які операції можна виконувати над множинами?
5. Як додати елемент в Множину?
6. Як виключити елемент з Множини?
7. Як вивести елементи множини?
Література:
Фаронов В.В. Турбо Паскаль 7.0. Начальный курстор. – М: Диалектика, 1997. – 487 стор. 103-107
Урок № 32
(згідно робочої навчальної програми)