Статистичнi I динамiчнi структури даних

 

Завдання: розробити алгоритми і написати програми, що реалізовують роботу магазинного і кільцевого стеків. У програмі передбачити дві версії: статичну і динамічну.

 

Стеком називається виділена (програмістом) область ОЗУ, для якої програмно організовані спеціальні режими функціонування:

-магазинний стек з дисципліною обслуговування "першим прийшов - останнім вийшов"

(FILO - first in, last out), або

-кільцевий стек з дисципліною "першим прийшов - першим вийшов" (FIFO - first in, first out).

 

 

Магазинний стек з дисципліною FILO.

Магазинний стек з дисципліною FILO <першим прийшов - останнім вийшов> є структурою з N виділених в ОЗУ під стек елементів (ЯП) пам'яті і одного покажчика W вершиною стека, що є:

На логічному рівні робота стека FILO організована так, що операція запису-читання в/із стека завжди адресується до однієї і тієї ж ЯП - вершині стека W - і супроводжується для збереження попередньої інформації одночасним (паралельним) перенесенням (витісненням) вмісту молодших ЯП в старших при записі і навпаки із старших в молодших при читанні.

На фізичному рівні робота стека реалізується виключно просто і без

яких-небудь перезаписів або обмінів вмістом між ЯП, виділеними в ОЗУ під стек, а саме інкрементом/декрементом покажчика вершини W стека (продумайте це!).

 

 

Алгоритм Стек_filo (магазинний стек)

Організовує і підтримує стекову пам'ять з дисципліною обслуговування <першим прийшов - останнім вийшов>.

Прийоми програмування - покажчики і заглушки.

 

Крок 0. Початок.

Крок 1. Модуль диспетчера:

[ініціалізація покажчиків і пам'яті]

W = 0 (покажчик вершини стека)

input <Кількість елементів пам'яті під стек N=> N

dim S(N) (резервування пам'яті, S(i) - що зберігається в i-й ЯП дане)

DIALOG: [інтерфейс з користувачем]

print < Вкажіть вид операції:>

print < вписати дане в стек (1)>

print < видати дане із стека (2)>

print < друк вмісту стека (3)>

print < кінець роботи (4)>

input O: on O goto WWOD, WUWOD, PRT, ENDE

else goto DIALOG.

 

Крок 2. Модуль запису даного в стек:

WWOD:

input <Введіть даного M=> M

W = W + 1 (інкремент покажчика вершини)

[заглушка для запобігання виходу покажчика W за межі стека]

if W > N then [повідомлення про помилку]

print <ПЕРЕПОВНЮВАННЯ СТЕКА!>

[відновлення значення покажчика вершини]

W = W - 1

else S(W)= M (запис даного в стек) fi

 

Крок 3. Модуль читання даного із стека:

WUWOD:

[заглушка для виродженого випадку "порожній стек"]

if W = 0 then [повідомлення про помилку]

print <СТЕК ПОРОЖНІЙ!>

else

[видача даного із стека, звільнення ЯП(тільки у учбових цілях для наочності роботи модуля 4 - друк вмісту стека) і декремент покажчика вершини]

M = S(W) and S(W)=0 and W = W - 1 and print M

Fi

 

Крок 4. Модуль друку вмісту стека:

PRT:

print <Вершина стека W=> W

for I = 1 to N do

print S(i)

od

goto DIALOG.

 

Крок 5. Кінець:

ENDE: end.

 

КІЛЬЦЕВИЙ СТЕК з дисципліною FIFO

 

Кільцевий стек з дисципліною FIFO <першим прийшов - першим вийшов> є структурою з N виділених під стек ЯП і двох покажчиків:

F (first) - для вказівки ЯП, що містить перше записане в стек дане

і L (last) - для вказівки ЯП, що містить останнє записане в стек дане (в порядку надходження останніх):

 

Для запису чергового даного в стек досить виконати інкремент покажчика L і занести це дане в ЯП, на яку показуватиме L, а для читання - вивести вміст ЯП, на яку показує покажчик F, і потім виконати інкремент F, щоб забезпечити читання наступне дане. При цьому, для уникнення непорозумінь необхідно кожного разу відстежувати положення F і L щодо один одного і меж стека:

 

(i) досягнення L верхньої межі N ще не означає, що в стек більше не можна записувати дані, оскільки в межі N-1 попередніх ЯП можуть бути вже порожніми і використовуватися повторно. Тому після запису даного в ЯП з номером L=n і

(ii) необхідності запису наступного даного L повертається в початок стека і порівнюється з F: якщо L=f, то стек заповнений повністю і подальший запис в нього не можливий. Тоді L необхідно повернути на колишнє місце і вивести повідомлення про помилку СТЕК ПЕРЕПОВНЕНИЙ, інакше - продовжити працю стека за описаною схемою;

(iii) при читанні кожного разу необхідно порівнювати F з L і при F>l видати повідомлення про помилку СТЕК ПОРОЖНІЙ, а F повернути на колишнє місце. Крім того при F>n його алогічно L також необхідно перемістити в початок стека і повторити (iii) спочатку;

(iv) і, нарешті, при записі одночасне F=l=0 означає вiдсутнiсть стека і вимагає його створення (ініціалізації).

 

ЛАБОРАТОРНА РОБОТА № 13

ЛАБІРИНТ

Завдання: розробити алгоритми і написати програми, проходження через лабіринт. Розглянути дві версії: евристику лівої руки і метод ковзаючого вікна.

 

Версія 1. Евристика лівою руки. Щоб пройти лабіринт до виходу з нього або повернутися в точку входу, коли проходу з даної початкової точки немає (тобто не заблукати!), необхідно рухатися весь час торкаючись стіни лівою рукою (продумайте це!)

 

Представлення даних:

вхідні дані: бінарна матриця L (M,n)‚ де:

M - кількість рядків (висота лабіринту)

N - кількість стовпців (ширина лабіринту)

s - індекс рядка

до - індекс стовпця

L (s, до) = 1 - прохід

L (s, до) = 0 - стіна

 

s (рядок)

­ß V (вхід)

0 1 0 0 0 0

0 1 1 1 1 0

0 0 1 0 0 0 (можливий вихід)

0 0 1 1 1 1 Þ W1

(можливий вихід) W3 Ü 1 1 1 0 0 0

0 0 1 0 0 0

ß k (колонка)

W2 (можливий вихід)

 

V, наприклад, V = L(1,2) - точка входу

Н - напрям, з якого увійшли до лабіринту (далі - в поточну крапку)

Н::= 1, якщо прибув зверху

Н::= 2, якщо прибув справа

Н::= 3, якщо прибув знизу і

Н::= 4, якщо прибув зліва.

вихідні дані:

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

(X(i) - горизонтальна, Y(i) - вертикальна)

прохідних точок лабіринту аж до досягнення граничної крапки.

Граничною крапкою (вона ж точка виходу з лабіринту) є крапка, для якої

s = 1 або s = m або до = 1 або до = n (продумайте це!)

тобто умовою завершення роботи є досягнення граничної крапки:

Ідея рішення і її формалізація:

евристика лівої руки - рухатися в лабіринті весь час тримаючись стіни лівою рукою

1) гарантує відшукання виходу, якщо він є, або повернення в початкову точку, якщо виходу немає

2) не гарантує знаходження глобального екстремуму, тобто знайдений маршрут не обов'язково є найкоротшим (наприклад, з V(1,2) може бути знайдений тільки вихід W1 за 12 кроків 1-2-3-4-5-4-3-6-7-8-9-10, а найближчий вихід W2, доступний за 7 кроків 1-2-3-6-7-13-14, знайти неможливо:

 

 

ß V

0 1 0 0 0 0

0 2 3 4 5 0

0 0 6 0 0 0

0 0 7 8 9 10 Þ W1

W3 Ü 11 12 13 0 0 0

0 0 14 0 0 0

ß W2

 

3) дуже просто формалізується за допомогою прапора Н = <напрям прибуття>. Дійсно, абстрактний оператор <рухатися весь час тримаючись стіни лівою рукою>

означає одне і лише одне: з кожної чергової i-й точки лабіринту необхідно намагатися пройти спочатку вліво, потім - прямо, управо або назад і обов'язково у вказаному порядку, а для цього і потрібний прапор напряму прибуття.

 

Наприклад, якщо ми прийшли в i-ю крапку зверху, то евристика лівої руки припускає наступну схему спроб відшукання i+1 точки шляху через лабіринт

 

 

s

Н = 3 повернення ­ ¯ напрям прибуття Н = 1

s = s - 1, k = k

1-а спроба

3-а спроба i ® H = 4

H = 2 s = s, k = k + 1

s = s, k = k - 1 ¯

­

2-а спроба Н=1­, s = s + 1, k = k k

 

в результаті евристика може бути реалізована, наприклад, таким чином

(i) ввести напрям і координати точки входу input H, s і до;

(ii) запам'ятати першу точку шляху через лабіринт i = 1, X(i)= до, Y(i)= s;

(iii) цикл пошуку

do

case H

1: <прибувЗверху>

2: <прибувСправа>

3: <прибувЗнизу>

4: <прибувЗлiва>

fi; inc(i)

until s=1 or s=m or k=1 or k=n od;

(iv) виведення маршруту:

print <маршрут через лабіринт >; for j=1 to i do writeln (X(j), Y(j)) od;

 

Залежно від напряму прибуття перемикач H викликає один з операторів: <прибувЗверху >, < прибувСправа>, <прибувЗнизу> або < прибувЗлiва >.

 

Всі ці оператори виконують одне і те ж: перевіряють за годинниковою стрілкою сусідні клітки і залежно від того, яка з них першою

виявиться прохідною, викликає відповідного оператора <йтивправо>, <йтивниз>, <йтивліво> або <йтиверх>

 

do <прибув Зверху>:

if L(s, k + 1) = 1 then <йтиВправо>; break fi

if L(s + 1, k) = 1 then <йтиВниз>; break fi

if L(s, k - 1) = 1 then <йтиВліво>; break fi

<йтиВерх> 'назад

Od

 

do <прибувСправа>:

if L(s + 1, k) = 1 then <йтиВниз>; break fi

if L(s, k - 1) = 1 then <йтиВліво>; break fi

if L(s - 1, k) = 1 then <йтиВерх>; break fi

<йтиВправо> 'назад

Od

 

do <прибувЗнизу>:

if L(s, k - 1) = 1 then <йтиВліво>; break fi

if L(s - 1, k) = 1 then <йтиВерх>; break fi

if L(s, k + 1) = 1 then <йтиВправо>; break fi

<йтиВниз> 'назад

od

 

do <прибувЗліва>:

if L(s - 1, k) = 1 then <йтиВерх>; break fi

if L(s, k + 1) = 1 then <йтиВправо>; break fi

if L(s + 1, k) = 1 then <йтиВниз>; break fi

<йтиВліво> 'назад

od

 

оператори< йтиВправо>, < йтиВниз >, < йтиВліво > и < йтиВерх >, використовувані в операторах <прибувЗверху>, <прибувСправа>, <прибувЗнизу> і <прибувЗліва>, тривіально реалізуються через:

 

1) інкремент/декремент належної координати

2) інкремент індексу нової точки шляху через лабіринт і

3) відповідну модифікацію прапора напряму

 

другими словами:

do < йтиВправо >: H = 4; inc(i); inc(k); X(i) = k, Y(i) = s od

do < йтиВниз >: H = 1; inc(i); inc(s); X(i) = k, Y(i) = s od

do < йтиВліво >: H = 2; inc(i); dec(k); X(i) = k, Y(i) = s od

do < йтиВерх >: H = 3; inc(i); dec(s); X(i) = k, Y(i) = s od

 

Розробка решти модулів тривіальна і залишаємо її як домашнє завдання для лабораторної роботи.

 

 

 

ЛАБОРАТОРНА РОБОТА № 14

ЕВРИСТИКИ.

 

Завдання: розробити алгоритм і написати програму для завдання Аладдіна:

скільки цінних речей (заданих масою і ціною) може поміститися в рюкзак (заданий об'єм) Аладдіна.

 

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

 

Розглянемо евристику на прикладі завдання, для оптимальної архівації файлів на гнучких дискетах (тобто на мінімально можливій кількості останніх).

ДАНО: ємкість однієї дискети Е в кілобайтах і перелік з F файлів, заданих їх номерами I і їх довжинами D(I) в кілобайтах.

ПОТРІБНИЙ: перелік дискет у вигляді їх номерів {J}, в якому для кожної дискети вказана кількість записуваних на неї файлів K(J), перераховані (у вигляді їх номерів) записувані на неї файли

{D(I)} і залишок вільного місця в кілобайтах OST(J).

 

МЕТОД РІШЕННЯ - евристика Грехема: черговий файл з впорядкованого по убуванню довжин списку файлів поміщається на ту дискету, на якій в результаті цього залишається найменше вільне місце.

 

ПРЕДСТАВЛЕННЯ РЕЗУЛЬТАТІВ: оптимальний розподіл файлів по дискетах, що вимагає найменшої кількості останніх, представляється алгоритм у вигляді таблиці, в рядки якої, що відповідають відповідним дискетам, вписані номери файлів, які слід записати на цю дискету. У першій колонці цієї таблиці можна було б записувати номери дискет, а в останній - залишок вільного місця, але для змістовної простоти алгоритм ці стовпці виділені у відповідні окремі списки.

 

Декомпозиція завдання:

 

 

Крок 0. Початок.

Крок 1. Настройка АЛГ.

Крок 2. Введення і запам'ятовування номерів і довжин файлів.

Крок 3. Сортування файлів по збуванню їх довжин.

Крок 4. Розподіл файлів по дискетах.

Крок 5. Виведення результатів.

Крок 6. Кінець.

 

Декомпозиція кроків:

Крок 1. Настройка алгоритму:

1.1. ввести ємкість дискети в кілобайтах: input e

1.2. ввести кількість файлів: input f

1.3. резервувати пам'ять:

df(f, f) - масив "дискета-файли", що містить перелік файлів, записуваних на кожну дискету.

Тут і далі об'єм резервованої пам'яті визначається гіршим випадком, коли на одну дискету поміщається тільки один файл;

 

n(f) - список номерів файлів, що архівуються;

d(f) - список довжин файлів, що архівуються;

до(f) - список кількості файлів на кожній дискеті;

ost(f) - список залишків вільного місця на кожній дискеті.

 

Крок 2. Введення і запам'ятовування номерів і довжин файлів:

for i = 1 to f do

n(i) = i and ost(i) = e and k(i) = 0

input d(i) (довжина i-го файлу)

Mf: if d(i) > e then

print < Дуже довгий файл!>

input d(i) и goto Mf fi od.

 

Крок 3. Сортування файлів по убуванню їх довжин

for UKZ = 1 to f do

IND = UKZ

for i = UKZ + 1 to f do

if d(i) > d(IND) then IND = i fi od

if IND <> UKZ then

a = d(UKZ): d(UKZ) = d(IND): d(IND) = a

a = n(UKZ): n(UKZ) = n(IND): n(IND) = a fi

od.

 

Крок 4. Розподіл файлів по дискетах:

[перебір файлів]

for i = 1 to f do

[ підготовка алгоритму МІНІМУМ для пошуку дискети,

розміщення на якій i-го файлу дасть найменший залишок вільного місця]

min = e (min - найменше вільне місце)

q = 1 (q - дискета з найменшим залишком)

[перебір дискет]

for j = 1 to f do

z = ost(j) - d(i) (поточний залишок, тобто вільне місце на j-й диске-

ті при записі на неї i-го файлу)

if z >= 0 AND z < min then

q = j and min = z fi

[інакше - до наступної дискети] od.

[проглядання дискет завершене, тому запис чергового проміжного результата]

k(q) = k(q) + 1 (інкремент числа файлів на q-й дискеті)

p = k(q) (службова змінна для передачі індексу)

df(q,p) = n(i) (запис на q-у дискету i-го файлу)

ost(q) = min (запис на q-у дискету нового значення залишку)

[до наступного файлу] od.

 

Крок 5. Виведення результатів.

 

ЛАБОРАТОРНА РОБОТА № 15

КЛАСИ

 

 

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

 

Клас в ООП - це структурний тип даних, який включає опис полів даних, процедур і функцій, що працюють з цими полями даних.

Визначення класу в Borland Pascal 7.0 здійснюється в два етапи. На першому етапі описується структура класу, де указуються: ім'я класу, поля даних і прототипи (заголовки) методів:

 

TYPE

<ім'я класу> = object

<ім'я поля даних 1>: <тип даних 1>;

..

<ім'я поля даних N>: < тип даних N>;

Procedure <ім'я методу 1>(<список параметрів>);

Function <ім'я методу 2>(<список параметрів>):<тип функції>;

Procedure <ім'я методу L>(<список параметрів>);

Function <ім'я методу М>(<список параметрів>):<тип функції>;

End;

Поля даних класу можуть бути наступних типів: числового; логічного; символьного; строкового адресного); типу діапазон; множина; масив; файл; клас; покажчик на клас; і ін.

Методами є процедури і функції мови Borland Pascal 7.0. У описі структури класу указуються тільки заголовки методів (ім'я процедури або функції, список передаваних параметрів, тип функції).

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

 

 

Procedure <ім'я класу>.< ім'я методу>;

<опис локальних змінних, процедур і функцій >

Begin <оператори> End;

Function <ім'я класу>.< ім'я методу>;

<опис локальних змінних, процедур і функцій>

Begin <оператори> End;

Дані і методи описуються в одному класі. Таке оголошення об'єднує дані з процедурами і функціями, що маніпулюють цими даними. При цьому всі дані, описані усередині класу, автоматично стають глобальними по відношенню до його методів, тобто загальнодоступними як для процедур, так і для функцій класу. Описавши новий тип - клас, ми дістаємо можливість оголошувати змінні цього класу. Змінну типу класу прийнято називати екземпляром класу або об'єктом.

 

 

Наслідування

Наслідування -це таке співвідношення між класами, коли один клас використовує структурну або функціональну частину одного або декількох інших класів (відповідно просте і множинне наслідування).

У Borland Pascal 7.0 реалізовано просте наслідування, при якому у класу може бути тільки один батько, але скільки завгодно нащадків.

Будь-який клас можна оголосити нащадком раніше описаного класу. Нащадок успадковує всі дані і методи класу батька і доповнює їх своїми даними і методами.

 

Поліморфізм

Borland Pascal реалізує механізми простого і складного поліморфізму.

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

У ООП вважається, що всі реалізації однойменних методів ієрархії утворюють поліморфний метод сімейства класів. Кожен варіант реалізації при цьому є окремим аспектом поліморфного методу сімейства класів. Конкретний аспект статичного поліморфного методу визначається типом об'єкту на етапі компіляції програми (раннє скріплення).

Складний поліморфізм. При складному поліморфізмі конкретний аспект поліморфного методу також визначається типом об'єкту, для якого він викликаний, але тільки не на етапі компіляції, а на етапі виконання програми (пізнє скріплення).

Необхідність пізнього скріплення обумовлена зокрема тим, що в Borland Pascal дозволяється покажчику на об'єкти класу-батька привласнювати адресу об'єкту класу-нащадка. Оскільки при передачі об'єктів як параметри використовуються покажчики, формально описаному параметру типу деякого класу може відповідати фактичний параметр не тільки того ж типу, але і типу класу, похідного від вказаного.

У тих випадках, коли реальний тип об'єкту не визначений, скріплення об'єкту і методу на етапі компіляції програми приводить до того, що за будь-яких умов (і для об'єктів батьківських класів, і для об'єктів похідних класів) викликається батьківський метод. Застосування пізнього скріплення дозволяє правильно визначити необхідний аспект поліморфного методу.

Поліморфні методи, для яких застосовується пізнє скріплення, називають віртуальними.

Для опису віртуальних методів використовується службове слово virtual:

 

Список тем для лабораторних робіт по ООП