Тема: Множинні типи.

Множина – це набір однотипних елементів. Множинний тип будується на основі деякого базового типу даних. Базовий тип повинен бути одним із порядкових типів. Він не повинен мати більше, ніж 256 можливих значень. Значення верхньої і нижньої границі базового типу не можуть виходити з діапазону від 0 до 255. У силу цього базовий тип множини не може бути коротким цілим (Shortint), цілим (Jnteger), довгим цілим (Longint) чи словом (Word).

Діапазон значень множинного типу – це набір всіх можливих підмножин множини елементів базового типу. Кожне можливе значення множинного типу є підмножиною можливих значень базового типу. Будь-який множинний тип може приймати значення [ ], яке називається порожньою множиною.

Опис множинного типу.

Опис множинного типу має вигляд:

<множинний тип> = set of < порядковий тип>

Приклади опису множинного типу:

type

М = set of 0..99; {множина може містити будь-який набір цілих чисел діапазону 0..99}

А = set of 'а' .. 'z'; {множина може містити будь-який набір символів з діапазону 'а' .. 'z'}

Dnі = (Рn, Vt, Sr, Cht, Pt, Sb, Ned); {Базовий тип}

В = set of Dni; {множина може містити будь-який набір елементів діапазонного типу Dnі}

С = set of Byte {множина може містити будь-який набір цілих чисел типу Byte}

Конструктори множин.

Щоб утворити конкретну множину, використовують конструктор множини. Конструктор множини дозволяє сформувати множину, яка містить певний набір елементів базового типу. Множина утворюється шляхом запису виразів або значень базового типу, які записані у квадратних дужках [ ]. Кожний вираз задає значення одного елемента множини. Між виразами чи значеннями ставиться кома. Будь-яка група елементів, описана, як х..у, оголошує елементами множини всі значення базового типу в діапазоні х..у. Якщо х більше, ніж у, то діапазон х..у не описує ніяких елементів і означає порожню множину. Синтаксис конструктора множини:

[<список елементів>]

У конкретному конструкторі множини всі значення виразів повинні належати до базового типу цієї множини. Конструктори множин здебільшого використовуються для швидкого формування множин за допомогою оператора присвоювання. Наведемо приклади конструкторів множин, типи яких описані в попередньому пункті

var

М1: М; М2: А; МЗ: В;

begin

...

М 1:=[ 1..10, 20, 30, 40, 50, 60, 70, 80, 90];

M2:=['a'..'f'];

М3:=[Рn, Vt, Cht, Pt];

…

end.

Операції над множинами.

Наведемо операції над множинами, враховуючи їх пріоритет:

перетин множин (позначається знаком *)

об'єднання множин (позначається знаком +), різниця множин (позначається знаком - ),

операція перевірки на приналежність до множини (позначається службовим словом іn) та операції порівняння (=, <>, <=, >= ).

Перетин множин А∩В – це множина, яка складається із спільних елементів обох множин. Позначається С:=А *В. Об'єднанням множин А і В є множина С, що складається з елементів, що належать хоча б одній з множин, А або В. Математичний вираз C=A B на мові Pascal виглядатиме С:=А+В. Різниця множин А\В – це множина, що складається з елементів множини А без елементів, що належать до множини В. Позначається С:=А-В.

Перераховані операції виконують над множинами і їх результат є також множина. Решта операцій, визначених над множинами – це логічні операції. Результатом їх є значення true або false, яке визначається істинністю чи ні певного твердження.

Операція перевірки на приналежність до множини (іn) має такий формат: А іn S, де А - вираз, S - множина. Результат виразу повинен мати тип, який є базовим по відношенню до множини. Результат цієї операції буде true, якщо вираз має значення, яке належить до множини.

Приклад (використовуючи попередні описи):

Рn іn М3 {Результат true}

9 іn Мl {Результат false}

Операції порівняння наведені в наступній таблиці.

Операція		Вираз	Результат
=	рівність множин	A=B	True, якщо множини А і В співпадають, еквівалентні
<>	нерівність множин	A<>B	True, якщо множини А і В не співпадають, нееквівалентні
<=	входження лівого аргументу в правий	A<=B	True, якщо А В, тобто перша множина включена в другу
>=	входження правого аргументу в лівий	A>=B	True, якщо А В, друга множина включається в першу множину

Існують дві процедури для роботи з множинами:

include (S, І), exclude (S, І).

Процедура include (S, І) включає елемент І у множину S, а exclude (S, і) - виключає елемент І з множини S.

3мінним типу множини можна присвоювати значення інших множин або виразів множинного типу. Необхідно тільки, щоб тип змінної і тип значення, що присвоюється, був однаковим. Множинні вирази (вирази, результат яких має множинний тип) складаються із звертань до змінних множинного типу, констант і конструкторів, а також з операторів об'єднання, різниці і перетину.

Константи множинного типу.

Якщо значення елементів множини відомі наперед, вона може бути оголошена в розділі констант:

<ідентифікатор константи> : <множинний тип> = [ <список елементів> ];

Список елементів може містить елементи базового типу, взяті у квадратні дужки і відокремлені комами. Як і для конструкторів множин, допускається використання діапазонів базового типу. Конструктори множин по вигляду близькі до множинних констант, але елементами їхнього списку можуть бути не тільки константи базового типу, але і довільні вирази цього типу. Наведемо кілька прикладів констант-множин:

type

С = set of 0..9;

L = set of 'A'..'Z';

const

Раrnі: С = [0,2,4,6,8]; {парні цифри}

Golosni : L = ['A','E','I,'O',U','Y']; {голосні}

Множини-константи можуть зустрічатися в тексті програм і без попереднього опису. В цьому випадку в квадратних дужках просто перераховуються елементи цієї множини.

Приклади використання типу множина.

Приклад 1. Ввести з клавіатури послідовність малих латинських букв. Роздрукувати 1) введені букви в алфавітному порядку, 2) голосні, 3) приголосні.

program mnоz;

type Lеttегs = set of 'а'. .'z'; {всі букви}

const Gоlosnі : Letters = ['а','e','і','o','u','y'); {голосні}

vаr А, А 1, А2 : Letters; і : ‘a’..’z’; S : string; n, j : integer;

begin

wrіtеln('Введіть послідовність символів'); read(S);

n:=length(S);

А:=[]; {А - порожня множина}

for j := 1 to n dо

if S[j] іn ['a'..'z'] then A:=A+[S[j]]; {якщо і-й символ рядка S належить до множини-константи ['a'..'z'], то він додається до множини А}

wrіtеln('Друк елементів множини А:');

for і:='а' to 'і dо if і іn А then write(i:2);

writeln;

А1:= А*Golosni; {Утворення множини А1, яка складається з голосних літер}

wrіtеln('Друк голосних літер, що входять до множини А:');

for і :='а' to 'z' do if і іn А1 then write(i :2);

writeln;

А2:= А-А1; {Утворення множини А2, яка складається з приголосних літер}

wrіtеln ('Друк приголосних літер, шо входять до множини А:');

for і:='а' to 'z' do if і іn А2 then write(i:2);

еnd.

Приклад 2. Наведемо приклад невеликої програми, в якій використовується поняття множини. Програма реалізує знаходження декількох перших простих чисел методом "решета Ератосфена"

Program Eratosphen ;

Const N=256; {максимальна кількість перебраних натуральних чисел}

Var Sieve, {початкова множина}

Primas: set of 2..N; {результативна множина}

Next :byte; {робочі змінні}

J :word;

Begin

Sieve : = [2..N ]; {всі числа в заданому діапазоні}

Primes : = [ ]; {початкова порожня множина}

Next : = 2 ; {починаємо з мінімального простого}

repeat

{пошук наступного простого числа}

While not (Next in Sieve) do {шукаємо в Sieve найменше число}

Next: = Next +1 ;

Primes : = Primes + [Next]; {вставимо його в Primes}

J : = Next ;

While J < = N do

Begin

{Знищуємо з Sieve всі числа, кратні Next}

Sieve : = Sieve – [ j] ;

J : = J+ Next ;

End

While {повторюємо цикл до закінчення Sieve}

Sieve = [ ];

For J : = 2 to N do {виводимо на друкування отриманого Primes}

If J in Primes then write (J : 5)

End.

Питання для самоконтролю:

1. Що таке множина?

2. Який опис множинного типу?

3. Для чого використовують конструктор множини?

4. Які операції можна виконувати над множинами?

5. Що називається перетином, об’єднанням та різницею множин?

6. Який вигляд має операція перевірки на приналежність?

7. Як описуються константи множинного типу?

РОЗДІЛ ІІІ. ЗАГАЛЬНІ ВІДОМОСТІ ПРО С++.

ОСНОВНІ КОНСТРУКЦІЇ МОВИ ПРОГРАМУВАННЯ С++.