Самостійна підготовка до виконання лабораторної роботи. мета: ознайомитись з можливостями мови турбо паскаль (тр) в опрацюванні множин
ЛАБОРАТОРНА РОБОТА №7
ТЕМА: МОВА ПРОГРАМУВАННЯ ТУРБО ПАСКАЛЬ.
ОПРАЦЮВАННЯ МНОЖИН
МЕТА: Ознайомитись з можливостями мови Турбо Паскаль (ТР) в опрацюванні множин. Закріпити вивчений матеріал при створенні власних нескладних програм опрацювання множин.
ЗНАТИ:стандартні процедури і функції опрацювання множин у ТР;
ВМІТИ:створювати власні програми для опрацювання множин;
ОБЛАДНАННЯ: технічне забезпечення: ПЕОМ, програмне забезпечення: система програмування Turbo Pascal 6.0.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Множина (Set) – це структурований тип даних, який подає набір взаємопов’язаних за певною ознакою або групою ознак об’єктів, які можна розглядати як єдине ціле. Кожний об’єкт у множині називається елементом множини. Всі елементи множини повинні належати одному зі скалярних типів, крім дійсного. Цей тип називається базовим типом множини. Базовий тип задається діапазоном або переліком. Область значень типу множина – набір можливих підмножин, складених з елементів базового типу. Якщо базовий тип має N значень, то тип множина для нього буде мати 2N варіантів різних значень.
Для опису множинного типу використовується словосполучення Set of (множина з).
Формат:
Type
<ім’я типу> = Set of <базовий скалярний тип>;
Var
<ім’я змінної> : <ім’я типу>;
Можна задати множинний тип і без попереднього опису:
Var
<ім’я змінної>: Set of <базовий скалярний тип>;
Приклад.
Type
SetChar = Set of Char; {множина з символів}
SetByte = Set of Byte; {множина з чисел}
SetDigit = Set of 0..9; {множина з чисел від 0 до 9}
SetDChar = Set of '0'..'9'; {множина з символів '0', '1',…,'9'}
SetSpring = Set of (March, April, May); {множина з весняних місяців, базовий перелічувальний тип визначений користувачем};
SetGolosn = Set of ('А', 'О', 'У', 'І', 'Є', 'И', 'Ї' ); {множина з великих голосних літер}
В Турбо Паскалі дозволяється визначати множини, які складаються не більше, ніж з 256 елементів. Стільки ж елементів містять типи Byte (0..255) i Char, і це ж число є обмеженням кількості елементів у будь–якому іншому перелічувальному базовому типі множини, який задає користувач. Кожному елементу перелічувального типу приписується певний номер. Для типу Byte номер дорівнює значенню числа, у типі Char номером символа є його ASCII–код. Нумерація здійснюється від 0 до 255. З цієй причини не можуть бути базовими для множин типи ShortInt(–128..127), Word(0..65535), Integer(–32768..32767), LongInt( –2147483648..2147483647).
Змінна типу множина підлягає певному синтаксису. Елементи множини повинні братися у квадратні дужки.
Приклад.
SByte := [1,2,3,4,10,20,30,40];
SChar := ['a', 'b', 'c'];
SChar := [ 'd'];
SSpring := [April];
SDiap := [1..4]; {те ж саме, що [1,2,3,4]}
SComp := [1..4, 5,7,10..20];
Empty := [];
Порожня множина записується як [].
Порядок слідування елементів всередині дужок не має значення, не має значення і кількість повторення елементів. Повторні входження елементів ігноруються.
Так, записи ['a','b','b','a'] i ['a','b'] еквівалентні.
Операції над множинами
| НАЗВА | ФОРМА | ПОЯСНЕННЯ, ПРИКЛАДИ ВИКОРИСТАННЯ | |
| = | Перевірка на рівність | S1 = S2 | Результатом є логічне значення, рівне TRUE, якщо S1 і S2 складаються з однакових елементів незалежно від порядку слідування, і FALSE у протилежному випадку. [1,2,3] = [1,3,2]; [] = []; ['a'..'c'] = ['a','b','c'] |
| <> | Перевірка на нерівність | S1<>S2 | Результатом є логічне значення, рівне TRUE, якщо S1 і S2 відрізняються хоча б одним елементом, і FALSE у протилежному випадку. [1,2] <> [1]; [] <> [3]; ['a'..'c'] <> ['a','c'] |
| <= | Перевірка на підмножину | S1<=S2 | Результатом є логічне значення, рівне TRUE, якщо всі елементи S1 містяться і в S2 незалежно від їх порядку слідування, і FALSE у протилежному випадку. ['a','b'] <= ['a'..'z']; [] <= [4]; [1,2] <= [1,2,3] |
| >= | Перевірка на надмножину | S1>=S2 | Результатом є логічне значення, рівне TRUE, якщо всі елементи S2 містяться в S1, і FALSE у протилежному випадку. ['x'..'z'] >=['y']; [1..10] >=[1..5]; [5,7] >=[] |
| in | Перевірка входження елемента у множину | E in […] E in S1 | Результатом є логічне значення, рівне TRUE, якщо значення Е належить базовому типу множини і входитьу множину […] (S1). Якщо множина не містить у собі значення К, то результатом є FALSE. 5 in [0..5]; 's' in ['a'..'z']; not (7 in [9..20]) |
| + | Об’єднання множин | S1 + S2 | Результатом об’єднання є множина, отримана злиттям елементів цих множин і виключенням елементів, що повторюються. [1,2]+[2,3,4] = [1,2,3,4]; {[1..4]} ['s'] + [] = ['s'] |
| – | Різниця множин | S1 – S2 | Результатом операції отримання різниці S1 – S2 є множина, складена з елементів, які входять в S1, але не входять в S2. [5,7,9] – [7] = [5,9]; ['1','2'] – ['8','9'] = ['1','2'] |
| * | Перетин множин | S1 * S2 | Результатом перетину є множина, що складається лише з тих елементів S1 і S2, які містяться одночасно і у S1, і у S2. [3,4,5,6,7] * [4,5,8] = [4,5]; ['x'] * [] = [] |
Переваги типу множина: компактність подання – один елемент множини займає один біт пам’яті; відсутність необхідності заздалегідь вказувати кількість елементів множини – по ходу програми множина може розширятись або скорочуватись; покращення наочності програм і гнучкості мови програмування. Основним недоліком є те, що Турбо Паскаль не дозволяє виводити множини на екран і отримувати окремі елементи з множин. Введення множин можливе лише по елементам.
Розглянемо прості приклади використання типу даних множина при розв’язуванні задач засобами мови ТР.
Задача 1. В порядку спадання вивести всі цілі числа з діапазону 1..4900, які можна подати у вигляді n2 + 2k2, але не можна подати у вигляді 7ij + j + 3 (n, k, i, j ≥ 0).
Uses Crt;
Type S = 1..4900;
SS = Set of S;
Var p: S;
S1, S2: SS;
n, k : integer;
Begin
S1 :=[]; S2 :=[]; {Ініціалізація множин}
for n:= 0 to 70 do
for k:= n to 70 do
begin
S1 := S1 +[n*n +2*k*k];
S2 := S2 + [7*n*k + k + 3]
end;
for p := 4900 downto 1 do
if (p in S1) and (not (p in S2))
then writeln(p)
End.
Задача 2. Дана послідовність латинських літер, яка закінчується крапкою. Вивести перші входження літер у послідовність, зберігаючи їх початковий взаємний порядок. (Наприклад, вхідний текст – qqwerrtyy., вихідний текст – qwerty).
Uses Crt;
Var Let : Set of 'a'..'z';
ch : Char;
Begin
ClrScr;
Let := []; {Множина літер у розглянутій частині тексту}
Read(ch);
while ch <> '.' do
begin
if not (ch in Let) then {Перше входження літери}
begin
Write(ch);
Let := Let + [ch]
end;
Read(ch)
end
End.
САМОСТІЙНА ПІДГОТОВКА ДО ВИКОНАННЯ ЛАБОРАТОРНОЇ РОБОТИ
1. Записати в зошит тему, мету, обладнання, практичні завдання свого варіанту (вибирається згідно номеру комп’ютера.) .
2. По літературі до лабораторної роботи з’ясувати контрольні теоретичні запитання.
3. По інструкції до лабораторної роботи ознайомитись з порядком виконання роботи.
ПОРЯДОК ВИКОНАННЯ РОБОТИ:
1. Ввімкнути комп’ютер.
2. Запустити Turbo Pascal.