Множини

Множина – це структурований тип даних, елементами якого є всі підмножини, побудовані на основі елементів базового типу.

Наприклад, множина, базовими для якої є елементи , складається з підмножин

,

де – порожня множина.

Всі підмножини множини різні й невпорядковані, тому підмножини і – еквівалентні. Кількість елементів базового типу, на основі якого конструюється множинний тип, називається потужністю і не може перевищувати .

У програмі опис множини має вигляд

<ім’я типу> = set of <базовий тип>;

де <ім’я типу> – ідентифікатор, set, of – зарезервовані слова (множина, із), <базовий тип> – будь-який порядковий тип крім Word, Integer, LongInt.

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

Type Ts = set of char;

Var s: Ts;

s1: set of 0..9;

s:= [‘a’..’z’]; {множина всіх підмножин із малих латинських літер}

s1:= [1..3, 7, 9]; {множина всіх підмножин із цифр 1,2,3,7,9}

Над множинами визначені такі операції:

· – перевірка еквівалентності; результат , якщо множини еквівалентні, інакше ;

· – перевірка нееквівалентності; результат , якщо множини нееквівалентні, інакше ;

· – перевірка входження; результат , якщо множина включає множину , інакше ;

· – перевірка входження; результат , якщо множина включає множину , інакше ;

· – перевірка належності; результат , якщо елемент міститься у множині , інакше ;

· – перетин множин; результат – множина спільних елементів і ;

· – об’єднання множин; результат – множина елементів доповнена тими елементами , яких немає в ;

· – різниця множин; результат – множина елементів , яких немає в .

Окрім зазначених операцій можна використовувати процедуру – добавити елемент у множину S та процедуру – вилучити елемент із множини S.

Приклад.Задано натуральне число . Розробити програму, яка друкує у зростаючому порядку всі цифри, які входять в це число, які не входять в це число і які входять в це число більше одного разу.

Для побудови згаданих множин виділяємо цифри у заданому числі. Для цього послідовно ділимо це число за модулем 10 (операція mod) і ділимо націло на 10 (операція div). Остачі від ділення за модулем 10 є цифрами цього числа. Добавляємо ці цифри у множину s1. Якщо така цифра вже є в множині s1, то добавляємо її у множину s3 – цифр, що повторюються. Множину s2 – цифр, яких немає в числі, одержимо як різницю множини-сталої c – всіх цифр і множини s1.

Для реалізації описаного алгоритму командою File|New Application створимо новий проект.

Рис. 6.1 Форма Пошук цифр

Присвоїмо формі заголовок Пошук цифр (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB6_1.pas, а проект – PLAB6_1.dpr.

Розробимо форму для введення початкових даних і виведення результату Рис.6.1.

Для введення початкових даних і виведення результату розмістимо на формі чотири компоненти Edit.

Крім цього, розмістимо на формі дві керуючі кнопки (компонент Button) з написами Обчислити, Вихід.

Обробник кнопки Обчислити міститься у програмному модулі ULAB6_1 і має вигляд:

Unit ULAB6_1;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

{Обробник кнопки Обчислити}

procedure TForm1.Button1Click(Sender: TObject);

Const c=[0..9];

Var n, i, k: integer;

s1, s2, s3: set of 0..9;

begin

{Введення початкових даних}

n:=StrToInt(Edit1.Text);

s1:=[]; {Множина цифр, які є в числі}

s2:=[]; {Множина цифр, яких немає в числі}

s3:=[]; {Множина цифр, які є в числі і повторюються}

i:=n;

while i<>0 do

begin

k:=i mod 10;

if k in s1 then s3:=s3+[k] else s1:=s1+[k];

i:=i div 10;

end;

s2:=c-s1;

{Виведення результату}

Edit2.Text:=''; Edit3.Text:=''; Edit4.Text:='';

{ Цифри, які є в числі }

for i:=0 to 9 do

if i in s1 then Edit2.Text:=Edit2.Text+IntToStr(i)+' ';

{ Цифр, яких немає в числі }

for i:=0 to 9 do

if i in s2 then Edit3.Text:=Edit3.Text+IntToStr(i)+' ';

{Цифри, що повторюються}

for i:=0 to 9 do

if i in s3 then Edit4.Text:=Edit4.Text+IntToStr(i)+' ';

end;