4 Вихідні дані роботи

Вершини дерева задаються літерами. Ознака кінця тексту - точка. Порожні піддерева позначаються зірочками, тобто задається вид дерева.

5 Хід виконання практичної роботи

Прикладом програми з використанням вкладених підпрограм-процедур може бути програма Demo_Tower, в якій реалізовано алгоритм стародавньої гри "Ханойські вежі". Є три стержні, на одному з них (наприклад, на лівому) засаджені диски різних розмірів, причому диски розташовуються так, щоб стрижень з дисками нагадував вежу, тобто внизу розташовуються найбільші диски, а вгорі маленькі. Мета гри-перенести вежу з правого стрижня на лівий, причому за один раз можна переносити тільки один диск і при цьому можна насаджувати тільки диск з меншим діаметром на диск з великим діаметром. Середній стрижень є допоміжним для тимчасового зберігання дисків.

program Demo_Tower; {Ханойські вежі-перенести кільця з правого стрижня - 3 на лівий - 1}

Type

Position = (Left, Centre, Right);

var

N: integer;

procedure MoveDisk (From, Tol: Position); {Переміщення диска}

procedure WritePos (P: Position); {процедура WritePos всередині процедури MoveDisk}

begin

case P of

Left: Write ('1 ');

Centre: Write ('2 ');

Right: Write ('3 ');

end;

end;

begin {початок процедури MoveDisk}

WritePos (From);

Write (':');

WritePos (Tol);

Writein;

end;

procedure MoveTower (Hight: integer; From, Tol, Work: position);

begin

if Hight> 0 then

begin

{Рекурсивний виклик}

MoveTower (Hight-1, From, Work, Tol);

MoveDisk (From, Tol);

{Рекурсивний виклик}

MoveTower (Hight-1, Work, Тоl, From);

end;

end;

Begin {Основна програма}

Writeln ('Введіть число кілець:');

Readln (N);

MoveTower (N, Right, Left, Centre); {Виклик процедури з передачею їй фактичних параметрів}

end.

Питання до захисту :

Що таке рекурсія?

Відповідь:____________________________________________________

_____________________________________________________________

Які співвідношення називають рекурентними?

Відповідь:____________________________________________________

_____________________________________________________________

Що називається глибиною рекурсії?

Відповідь:____________________________________________________

_____________________________________________________________

Сформулюйте основні вимоги до рекурсивним підпрограм.

Відповідь:____________________________________________________

_____________________________________________________________

Роботу виконав Роботу перевірив

Лабораторна робота №6 «Бінарне дерево пошуку»

1 Тема роботи: Підрахунок входжень кожного символу у текстовий файл за допомогою бінарного дерева пошуку

2 Мета роботи: Підрахувати кількість входжень кожного символу у текстовий файл, користуючись деревом пошуку.

3 Теоретичний матеріал

Дерево - це граф, який характеризується наступними властивостями:

1. Існує єдиний елемент (вузол або вершина), на який не посилається ніякий інший елемент - і який називається КОРН.

2. Починаючи з кореня і слідуючи певної ланцюжку покажчиків, що містяться в елементах, можна здійснити доступ до будь-якого елементу структури.

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

Назва "дерево" виникає з логічної еквівалентності деревовидної структури абстрактного дереву в теорії графів. Лінія зв'язку між парою вузлів дерева називається зазвичай гілок. Ті вузли, які не посилаються ні на які інші вузли дерева, називаються листям (або термінальними вершинами). Вузол, який не є листом або коренем, вважається проміжним або вузлом розгалуження (нетермінальний або внутрішньої вершиною).

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

Дерево пошуку будується за певним законом (див.рис. 6.1):

Рисунок 6.1 – Дерево пошуку

A, B і C тут - ключі пошуку. Якщо інформаційна частина вузла дерева - запис (а так буває в більшості випадків), то ключ - одне з полів.