Множинний тип

Begin

Begin

Repeat

End

End

End

Repeat

Begin

Begin

Begin

Масиви

1. Поняття масиву. Одномірні масиви

Масиви є представниками структурованих типів даних, тобто таких, змінні яких складаються з більш простих елементів відповідно до визначеного порядку. Для масивів характерно те, що вони є сукупністю деякого числа однакових елементів. У найпростішому випадку ці елементи можуть бути занумеровані натуральними числами з деякого діапазону. Розглянемо приклад такої змінної в Турбо Паскале:

var a: array [1..10] of real;

Змінна a складається з десяти елементів типу real, можна записувати і зчитувати значення з неї, користаючись записом a[< номер елементу >].

Приклад 1. Пошук найбільшого числа серед елементів масиву.

program FindMaximumInArray;

var a: array [1..10] of real;

i,max: integer;

for i:=1 to 10 do begin

write('Введіть елемент номер ',i,' -> ');

readln(a[i]);

end;

max:=a[1];

for i:=2 to 10 do

if a[i]>max then max:=a[i];

writeln('Максимум дорівнює ',max);

readln;

end.

Як тип елементів масиву можна використовувати всі типи, відомі нам на даний момент (до них відносяться всі числові, символьний, рядковий і логічний типи).

Нумерувати елементи масивів можна не тільки від одиниці, але і від будь-якого цілого числа. Узагалі для індексів масивів підходить будь-який порядковий тип, тобто такий, котрий у пам'яті машини представляється цілим числом. Єдине обмеження полягає в тому, що розмір масиву не повинний перевищувати 64 Кб. Розглянемо деякі приклади оголошення масивів.

var Numbers: array [0..1000] of integer;

Names: array [1..10] of string;

Crit: array [sh or tint] of boolean;

CountAll: array [char] of integer;

Count: array ['a'..'z'] of integer;

У наступному прикладі показане для чого може знадобитися останній тип.

Приклад 2. Підрахунок кількості різних букв у рядку.

program CountLetters;

var s: string;

count: array ['a'..'z'] of byte;

ch: char;

i: byte;

write('Уведіть рядок > ');

readln(s);

for i:=1 to length(s) do

if (s[i]>='a') and (s[i]<='z') then inc(count[s[i]]);

writeln('Кількість різних букв у рядку: ');

for ch:='a' to 'z' do

if count[ch]<>0 then

writeln(ch,': ',count[ch]);

readln;

end.

2. Багатомірні масиви

При необхідності можна нумерувати масиви не одним індексом а двома і більш. Двовимірному масиву відповідає матриця в математиці, тобто прямокутна таблиця.

Приклади описів багатомірних масивів:

var Matrix: array [1..4,1..3] of real;

Cube3D: array [1..5,1..5,1..5] of integer;

Розглянемо приклад використання двовимірного масиву.

Приклад 3. Побудувати календар на наступний рік, тобто при введенні номера місяця і числа видавати день тижня.

program Calendar;

type tWeekDay = (Mon,Tue,Wed,Thu,Fri,Sat,Sun,NoDay);

{NoDay - немає дня (наприклад, 30.02)}

tCalendar = array [1..12,1..31] of tWeekDay;

var CL: tCalendar;

m,d: byte; {місяць і число}

wd: tWeekDay; {день тижня}

{Будуємо масив:}

{1. Заповнимо весь календар значеннями "немає дня":}

for m:=1 to 12 do

for d:=1 to 31 do CL[m,d]:=NoDay;

{2. Будуємо масив-календар:}

m:=1; d:=1;

wd:=Mon;

CL[m,d]:=wd;

case m of

4,6,9,11: if d=30 then begin

m:=m+1;

d:=1;

else d:=d+1;

1,3,5,7,8,10,12: if d=31 then begin

m:=m+1;

d:=1;

else d:=d+1;

2: if d=28 then begin

m:=m+1;

d:=1;

else d:=d+1;

end;

wd:=tWeekDay((ord(wd)+1) mod 7);

until m=13;

{Виводимо на екран:}

write('Номер місяця > '); readln(m);

write('Число > '); readln(d);

case CL[m,d] of

Mon: writeln('Понедєльник');

Tue: writeln('Вівторок');

Wed: writeln('Середовище');

Thu: writeln('Четвер');

Fri: writeln('П'ятниця');

Sat: writeln('Субота');

Sun: writeln('Неділя');

NoDay: writeln('Такого дня немає в календарі');

end;

until false;

end.

3. Сортування і пошук

У прикладних програмах широко поширені два типи операцій, зв'язаних з масивами:

1. Впорядкування елементів масиву за зростанням чи спаданням (сортування)

2. Пошук елемента в масиві.

Розглянемо найпростіший варіант сортування масиву (сортування вибором). Нехай є масив з n елементів; спочатку знайдемо в ньому самий маленький серед елементів з номерами 2,3,...n і поміняємо місцями з першим елементом, потім серед елементів з номерами 3,4,...n знайдемо найменший і обміняємо з другим, і т.д. У результаті наш масив виявиться відсортованим по зростанню.

program SelectSort;

const n = 10;

var a: array [1..n] of integer;

i,j,jmin,buf: integer;

{jmin - номер найменшого елемента,

buf використовується при обміні значень двох елементів}

for i:=1 to 10 do begin

write('Введіть елемент номер ',i,' -> ');

readln(a[i]);

end;

for i:=1 to n-1 do begin

jmin:=i;

for j:=i+1 to n do

if a[j]<jmin then jmin:=j;

buf:=a[i];

a[i]:=a[jmin];

a[jmin]:=buf;

end;

write('Результат: ');

for i:=1 to 10 do write(a[i],' ');

readln;

end.

Інший спосіб — бульбашкове сортування, він працює трохи швидше, ніж попередній. На першому етапі рухаємося від n-го елемента до 2-го і для кожного з них перевіряємо, чи не менше він попереднього; якщо менше, те змінюємо місцями поточний і попередній. У підсумку перший елемент буде найменшим у масиві. На другому етапі також проходимо елементи від n-го до 3-го, на третьому — від n-го до 4-го, і т.д. У підсумку масив буде відсортований по зростанню.

program BubbleSort;

...

var i,j: integer;

buf: integer;

...

for i:=2 to n do

for j:=n downto i do

if a[j]<a[j-1] then begin

buf:=a[j];

a[j]:=a[j-1];

a[j-1]:=buf;

end;

end.

Множинні типи належать до трохи незвичного і порівняно рідко використовуваного засобу мови Pascal. Однак у ряді випадків використання множинних типів дозволяє помітно підвищити компактність і наочність програм.

Значення множинного типу, так само, як масиви, будуються з декількох значень одного (базового) типу. Однак, на відміну від масивів і записів, значення множинного типу може містити будь-яку кількість РІЗНИХ елементів базового типу - від нуля елементів (порожня множина) до всіх можливих значень базового типу. Іншими словами, можливими значеннями змінних множинного типу є ВСІ ПІДМНОЖИНИ значень базового типу.

Множинний тип задається за допомогою двох службових слів - set і of - і наступного за ним базового типу. Наприклад:

type

Digits = set of 1..5;

var

S: Digits;

Змінна s, визначена в прикладі, може приймати значення, що складаються з наступних сукупностей цілих чисел:

<порожня>

1, 2

1, 2, 3

1, 5

1, 3, 4, 5

3, 4, 5

1, 2, 3, 4, 5

Потрібно звернути увагу на дві обставини. По-перше, усі значення базового типу, що утворять конкретні значення множинного типу, повинні бути РІЗНІ. По-друге, порядок "розташування" елементів у множині ніяк НЕ ФІКСУЄТЬСЯ. Це відповідає прийнятому в математиці трактуванню множинм як безповторної неупорядкованої сукупності об'єктів.

Важливим є питання, з яких значень можна будувати множини, чи іншими словами, який може бути базовий тип множини. Авторська версія мови обмежується дискретними типами, однак практично всі реалізації сильно звужують це обмеження. Так, Turbo Pascal допускає як базові типи для множини дискретні типи не більш ніж з 256 різними значеннями, причому (для цілих типів) ці значення повинні лежати в діапазоні від 0 до 255. Таким обмеженням задовольняють тільки стандартні типи byte і char, перераховані типи, а також обмежені типи, утворені з них.

Приведемо ще один приклад опису множини:

type

ElemColor= (Red,Yellow,Blue);

Color= set of ElemColor;

var MyColor: Color;

Сукупність припустимих значень змінної MyColor містить наступні множини:

<nорожня множина>

Red

Yellow

Blue

Red, Yellow

Red, Blue

Yellow, Blue

Red, Yellow, Blue

У Pascal-програмі допускаються явні зображення значень множинних типів, подібно зображенням цілих чи дійсних чисел. Зображення множини (чи конструктор множини) будується зі списку елементів множини, розділених комами. Весь список обмежують квадратними дужками, наприклад:

[1,2,5] [Red,Yellow]

Як елементи в зображенні множини допускаються вирази, тип яких повинний збігатися з базовим типом множини.

Крім того, можна вказувати діапазони значень, що складаються з пари граничних значень, розділених знаком '..' (дві крапки); наприклад, два зображення множин [1..3,5] і [1,2,3,5] еквівалентні.

Порожня множина зображується двома квадратними дужками: [ ].

Необхідно пам'ятати, що множина - це безповторна сукупність елементів, так що, наприклад, три наступні зображення позначають одну і туж множину:

[1,2,3]

[1,1,2,3]

[1,2,3,2,2,3,1].

Приведемо ще кілька прикладів описів і зображень множин:

type

SetOfChar= set of char,-

Digits= set of 0..100; var

MyChars: SetOfChar;

MyDigl,MyDig2: Digits; begin

MyChars:= ['а'..'z','0'..'9','-'];

MyDigl:= [];

MyDig2:=MyDigl;

MyDigl:=[x..x+10,0,y-l,y+l];

Корисність того чи іншого типу даних визначається, у першу чергу, набором припустимих операцій над значеннями цих типів. Що стосується множинних типів, то тут маються наступні групи операцій:

· теоретико-множинне об'єднання, перетинання і віднімання множин;

· перевірка належності елемента множині;

· перевірка на рівність і нерівність множин;

· перевірка на входження (належність) однієї множини в іншій.

Розглянемо докладніше перераховані операції.

1. Об'єднання, перетинання і віднімання множин. Ці операції позначаються, відповідно, символами ’+’, ’*’ і ’-' і означають традиційні дії з множинами прийняті в математиці. Якщо представити дві множини А и В у виді прямокутників, то множину-результат перерахованих операцій можна наочно зобразити за допомогою зафарбованих частин цих прямокутників:

	об'єднання множин — множина, що складається з елементів, що належать множинам А и В.
	перетин множин — множина, що складається з елементів, що належать одночасно обом множинам.
	віднімання множин — множина, що складається з тих елементів однієї множини, що не належать іншій.

Наступний приклад ілюструє приведені операції (у правому стовпчику показана множина-результат операції):

[1,2] + [3,4] [1,2,3,4]

[1..10] + [5..15] [1..15]

[1..10] * [5..15] [5..10]

[1,2] * [3,4] []

[1..10] - [5..15] [1..4]

2. Перевірка належності до мнжини. Ця логічна операція позначається службовим словом in. Правий операнд повинний бути множиною, лівий - значенням базового типу множини. Операція видає true, якщо значення входить у множину, і false у противному випадку. Наприклад, наступні вирази:

2 in [1..10,12]

5 in [1,2,7,10]

видають відповідно true і false.

Операцію перевірки належності зручно використовувати для виключення більш складних перевірок. Наприклад, оператор виду

if (ch='а') or (ch='b') or (ch='х') or (ch='у') then S

може бути переписаний у більш компактній і наочній формі:

if ch in ['а','b','х','у'] then S

Помітимо, що другий варіант більш ефективний з погляду швидкодії.

3. Перевірки на рівність, нерівність і включення безлічей

= рівність (співпадання) двох множин

<> нерівність множин

<= перевірка на входження множини з лівого операнда в множину із правого операнда

>= перевірка на входження множини з правого операнда в множину з лівого операнда

Усі ці операції видають логічне значення true чи falae у залежності від успіху перевірки. Нижче приводяться приклади використання цих операцій.

[1,2,3] = [1,2] false

[1,2,3] >= [1,2] true

[S] <= [1..10] true, якщо 3 – ціле число з діапазону 1.. 10

[1,2,3] <> [1,2,2] true

Необхідно відзначити, що всі операції над множинами працюють досить ефективно, тому має сенс застосовувати їхній усюди, де це необхідно. На жаль, набір операцій над множинами в Раsсаl'е не містить принаймні однієї практично важливої операції - вибірки значення з множини (чи близько зв'язаного з нею засобу циклічного перебору значень множини). Тому при необхідності подібних дій приходиться організовувати цикл по всьому діапазоні значень базового типу, перевіряючи на кожній ітерації належність чергового значення даній множині, наприклад:

var

Symbols: set of char;

S: char; begin

for S:= chr(0) to chr(255) do

if S in Symbols then

<дії з змінною S>

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

program eratosfen;

uses crt;

const n=255;

var nath,kin:set of 2..n;

next:byte;

j:word;

Дата добавления: 2014-12-16