Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
БІНАРНЕ ДЕРЕВО ПОШУКУ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних
"БІНАРНЕ ДЕРЕВО ПОШУКУ"
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 7
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2010
Методичні вказівки до лабораторної роботи "Структура даних "БІНАРНЕ ДЕРЕВО ПОШУ-КУ"" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:
існує один виокремлений вузол - корень (root) дерева
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1.Tm і кожна з цих множин в свою чергу є деревом. Дерева T1.Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожна вершина є в свою чергу коренем деякого піддерева. Кількість піддерев вершини має назву ступеня (degree) цієї вершини. Вершина ступеню нуль має назву кінцевої (terminal) або листа (leaf). Некінцева вершина також має назву вершини розгалуження (branch node). Нехай x - довільна вершина дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вершини на цьому шляху називаються предками (ancestors) x; якщо деяка вершина y є предком x, то x називається нащадком (descendant) y. Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками. Кожну вершину x, в свою чергу, можна розглядати як корень деякого піддерево, елементами якого є вершини-нащадки x. Якщо вершини x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називається батьком (parent) до y, а y - сином (child) x. Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings). Вершини, що мають нащадків, називаються внутрішніми (internal). Глибиною вершини x називається довжина шляху від кореня до цієї вершини. Максимальна глибина вершин дерева називається висотою.
Якщо існує відносний порядок на піддеревах T1.Tm, то таке дерево називається впорядкованим (ordered tree) або пласким (plane tree).
Лісом (forest) називають множину дерев, які не перетинаються.
Найчастіше дерева в інформатиці зображують з коренем, який знаходиться зверху (говорять, що дерево в інформатиці "росте вниз").
Важливим окремим випадком кореневих дерев є бінарні дерева, які широко застосовуються в програмуванні і визначаються як множина вершин, яка має виокремлений корінь та два піддерева (праве та ліве), що не перетинаються, або є пустою множиною вершин (на відміну від звичайного дерева, яке не може бути пустим).
Важливими операціями на деревах є:
обхід вершин в різному порядку
перенумерація вершин
пошук елемента
додавання елемента у визначене місце в дереві
видалення елемента
видалення цілого фрагмента дерева
додавання цілого фрагмента дерева
знаходження кореня для будь-якої вершини
Найбільшого розповсюдження ці структури даних набули в тих задачах, де необхідне маніпулювання з ієрархічними даними, ефективний пошук в даних, їхнє структуроване зберігання та модифікація.
В програмуванні бінарне дерево - дерево, в якому кожна вершина має не більше двох синів. Зазвичай такі сини називаються правим та лівим. На базі бінарних дерев будуються такі структури, як бінарні дерева пошуку та бінарні купи.
Різновиди бінарних дерев :
Повне (закінчене) бінарне дерево - таке бінарне дерево, в якому кожна вершина має нуль або двох синів.
Ідеальне бінарне дерево -- це таке повне бінарне дерево, в якому листя (вершини без синів) лежать на однаковій глибині (відстані від кореня).
Бінарне дерево на кожному n-му рівні має від 1 до 2n вершин.
Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), симетричний (simetric) та зворотній (postorder).
Реалізація бінарних дерев :
Кожна вершина містить вказівники на правого та лівого сина (left та right)
Існують декілька варіантів конструювання бінарних дерев в залежності від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування. Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x разом з даними двох полів з вказівниками (правим та лівим) right[x] та left[x] на відповідних синів цієї вершини.
Модифікована реалізація бінарного дерева. Кожна вершина містить також вказівник на батьківську вершину
Також іноді додається вказівник p[x] на батьківську вершину. Це виявляється корисним, коли необхідний швидкий доступ до батьківської вершини та спрощує деякі алгоритми. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від синів до батьківської вершини. Деякі різновиди бінарних дерев (наприклад, червоно-чорні дерева або AVL-дерева), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутній один або обидва сини, відповідні вказівники ініціалізуються спеціальними "пустими" значеннями.
Бінарне дерево на базі масиву :
Бінарні дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її сини знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0). Інший варіант зберігання дерева в масиві — зберігати індекси нащадків.
Представлення n-арних дерев як бінарних :
Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в бінарне.
Для цього слід послідовно зв'язати усіх синів кожної сім'ї з першим сином та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першим сином в сім'ї. Тобто кожна вершина N впорядкованого n-арного дерева відповідає вершині M деякого бінарного дерева. Лівий син вершини M відповідає першому сину вершини N, а правий син M відповідає першому з наступних братів N (тобто першому з наступних синів батька вершини N).
Така відповідність має назву природної відповідності між n-арним та бінарним деревом.
Бінарне дерево пошуку:
Бінáрне дéрево пóшуку (англ. binary search tree, BST) в інформатиці - бінарне дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
нехай x - довільна вершина бінарного дерева пошуку;
якщо вершина y знаходиться в лівомі піддереві вершини x, то val[y] ≤ val[x];
якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритма центрованого обходу дерева. Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n -- розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h - висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).
Пошук в бінарному дереві :
Процедура пошуку в бінарному дереві отримує на вході значення k, яке необхідно знайти, та вказівник x на корень того піддерева, в якому слід шукати.
SEARCH (x, k)
if x = NULL or k = val[x]
then return x
if k < val[x]
then return SEARCH (left[x], k)
else return SEARCH (right[x], k)
В процесі пошуку ми рухаємось від кореня, порівнюючи значення k зі значенням в поточній вершині х. Якщо k < val[x], пошук рекурсивно продовжується в лівому піддереві (k може бути тільки там згідно умови впорядкованості), інакше -- у правому піддереві. Очевидно, що довжина шляху не перевищує висоти дерева, тому час пошуку є O(h), де h - висота дерева.
Мінімум, максимум, наступник та попередник :
Мінімальний елемент в дереві можна знайти, розглянувши послідовно ліве піддерево left[x]:
MINIMUM (x)
while left[x]<>NULL
do x:=left[x]
return x
Процедура знаходження максимуму симетрична. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h)
Елемент, що є наступним за даним (в сенсі відношення впорядкованості) можна знайти за допомогою такої процедури:
SUCCESSOR (x)
if right[x] <> NULL
then return MINIMUM (right[x])
y:=p[x]
while y<>NULL and x = right[y]
do x:=y
y:=p[y]
return y
Процедура знаходження попереднього даному елемента є симетричною. Обидві процедури знову ж таки знаходять елемент за час, пропорційний O(h).
Додавання елементу :
Процедура додавання елементу в бінарне дерево T додає елемент, зберігаючи умову впорядкованості. Параметром тут є вказівник z на нову вершину, в яку поміщене значення val[z], left[z]=right[z]=NULL.
INSERT (T, z)
y:=NIL
x:=root[T]
while x <> NULL
do y:=x
if val[z] < val[x]
then x:=left[x]
else x:=right[x]
p[z]:=NULL
if y = NULL
then root[T] :=z
else if val[z]<val[y]
then left[y]:=z
else right[y]:=z
Процедура рухається вниз по дереву, при цьому зберігаючи в y вказівник на батька вершини x. Порівнюючи значення в x та z, процедура вирішує, в яке з піддерев рухатись далі. Процес завершується тоді, коли x=NULL. Саме сюди й слід помістити вершину z (рядки 8-13). Ця операція також потребує часу для виконання, пропорційного O(h)
Видалення елементу :
Параметром для процедури є вказівник на вершину, що видаляється. Тут можливі три варіанти дій:
якщо у вершини немає синів, достатньо помістити NULL у відповідне поле його батька (замість вказівника на вершину, що видаляється);
якщо у вершини є один син, можна з'єднати батька цієї вершини безпосередньо з її сином;
якщо вершина має двох синів, слід спочатку знайти слідуючий (в сенсі порядку) елемент y, в якого немає лівого сина, а потім скопіювати значення та додаткові дані з вершини y на місце вершини, що видаляється, а саму вершину y видалити.
DELETE (T, z)
if left[z] = NULL or right[z]=NULL
then y:=z
else y:=SUCCESSOR(z)
if left[y] <> NULL
then x:=left[y]
else x:= right[y]
if x <> NULL
then p[x]:=p[y]
if p[y]:=NULL
then root[T]:=x
else if y=left[p[y]]
then left[p[y]] :=x
else right[p[y]]:=x
if y <> z
then val[z]:=val[y]
//копіювання додаткових даних з y
return y
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
Варіанти завдань:
Cтворити дзеркальне до заданого дерево.
Вилучити з дерева всi листки.
Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка.
Вилучити з дерева всi вузли, що мають двох синів.
Додати до дерева листки так, щоб воно стало строго бінарним деревом.
Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного.
Побудувати два бінарних дерева пошуку та визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї з його вершин.
Знайти середнє арифметичне значення всіх вузлів дерева.
Знайти середнє арифметичне значення всіх листків дерева.
Добудувати дерево до строго бінарного дерева.
Добудувати дерево до повного бінарного дерева.
Визначити, чи побудоване дерево є строго бінарним деревом.
Визначити, чи побудоване дерево є повним деревом.
Визначити, чи заданий вузол дерева є коренем, або листком, або вершиною.
Знайти найближчого спільного предка двох заданих вузлів дерева.
Знайти рівень заданого вузла дерева.
Знайти вузли, у яких кількість нащадків у лівому піддереві не дорівнює кількості нащадків у правому піддереві.
Знайти вузли, для яких висота лівого поддерева не дорівнює висоті правого піддерева.
Знайти довжину мінімального шляху між листами.
Знайти максимальний шлях між вузлами дерева.
ІІ. Завдання 2: Використовуючи побудоване в Завданні 1 бінарне дерево пошуку, розв'язати задачу згідно з варіантом.
Варіанти завдань:
1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку
послідовність:
2
6
4
7
9
Примітка: для всіх завдань замість номерів використовувати імена (текстові значення).
2. Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається.
Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі.
Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном).
3. В зовнішньому текстовому файлі записано програму на мові Паскаль. Відомо, що в цій програмі є ідентифікатори, кожний з яких містить не більше 9 латинських літер і/або цифр. Надрукувати в алфавітному порядку всі різні ідентифікатори цієї програми, вказавши для кожного з них число його входжень в текст програми (врахувати, що великі і малі букви ототожнюються, текст в середині коментарів не враховується, в записі дійсних чисел може зустрічатися літера Е або е ).
4. У деякій країні поліція виявила розгалужену мережу опозиційної партії. Партія сильно законспірована і складається з рядових членів і керівників різних рівнів. На чолі партії стоїть один головний керівник - лідер партії. Всі члени партії пронумеровані від 1 до N. Кожний член партії знає тільки свого безпосереднього керівника (рівно одного) і своїх безпосередніх підлеглих (керівник не знає підлеглих свого підлеглого і навпаки). До початку арештів наказ лідера може бути доведений до будь-якого члена партії. З початком арештів членів партії вона розпадеться на дрібні, не зв'язані один з одним групи. Поліцмейстер запевняє, що група, що складається з менш ніж K членів партії, ідеологічно вироджується і не становить погрози для держави. Прагнучи не упустити престиж країни в очах світової суспільної думки, поліцмейстер поставив задачу зробити мінімальну кількість арештів членів партії так, щоб від неї залишилися тільки маленькі групи.
Написати програму, яка б по вхідним даним, що знаходяться в текстовому файлі, описувала структуру підпільної партії і виводила кількість арештів і номери членів партії, яких потрібно заарештувати. При наявності декількох розв'язків вивести одне з них.
5. Написати програму реалізації гри Го-Моку. Це нескладна позиційна гра, яка відома зі стародавніх часів і, напевно, вперше виникла у Японії. Ця гра схожа на хрестики-нолики, але набагато цікавіша. За класичними правилами грають на дошці розміром 19x19 клітин (в програмі реалізуйте альтернативні варіанти: скорочений 9x9 та розширений 29x29 клітин). Гравці ставлять свої фішки на вільні клітини дошки по черзі. Виграє той, кому першому пощастить побудувати власну лінійку з п’яти фішок – горизонтальну, вертикальну або діагональну.
6. Задано рядок символів S і набір слів А[1], ..., A[k]. Написати програму розбиття рядка S на слова з набору всіма можливими способами.
Приклад: Вхідні дані Результат розбиття
S=ABBC S = A - B - BC
A[1]=A, S = A - BBC
A[2]=AB, S = AB - BC
A[3]=BC,
A[4]=BBC,
A[5]=H,
A[6]=B
7. N кісточок доміно за правилами гри викладаються в прямий ланцюжок, починаючи з кісточки, обраної довільним чином, в обидва кінці доти, поки це можливо. Змоделювати гру в доміно і написати програму
а) побудови самого довгого ланцюжка;
б) знаходження такого варіанта викладання кісточок, при якому до моменту, коли ланцюжок не можна далі продовжити, "на руках" залишиться максимальне число очок.
Приклад: Вхідні дані Результат
N= 5 5
1 2 56:62:21:13:36
1 3
2 6
3 6
5 6
8. Нехай задано n чоловіків і n жінок, та два n x n масиви P i Q таких, що P(і, j) вказує на надання переваги і-тим чоловіком j-тої жінки, а Q(i, j) – надання переваги і-тою жінкою j-го чоловіка. Написати програму знаходження таких паросполук чоловіків та жінок , щоб оптимізувати переваги.
9. Проблема призначення формулюється так: є n людей, що призначаються на n робіт. Вартість призначення i-людини до j-роботи - COST(i, j). Розробити алгоритм і написати програму, яка призначає кожній людині роботу, при мінімальній загальній вартості призначення.
10. Задано n завдань для виконання, але тільки k процесорів, що можуть працювати паралельно. Час, необхідний для виконання і-тої роботи, дорівнює ti. Написати програму, що визначає, які завдання на яких процесорах повинні бути виконані і в якому порядку, щоб остаточний час останнього завдання був мінімізований.
11. Широко відома гра "Міста". Називається яке-небудь місто, допустимо, "Львів". Це слово закінчується на букву "в", значить потрібно назвати інше місто, у якого в назві перша буква буде"в". Це може бути "Відень". Наступне місто повинно починатися на букву "н" і т.д. Заборонено повторювати назви міст. Написати програму, яка з послідовності назв міст (всі назви різні), що знаходиться в текстовому файлі, будує ланцюжок міст максимальної довжини.
Приклад: Вхідні дані (файл DATA.TXT) Результат
Львів Львів
Донецьк Відень
Харків Новгород
Київ Донецьк
Відень Київ
Ужгород
Новгород
12. Дано послідовність натуральних чисел ( значення кожного числа від 1 до 1000 ). Послідовність може бути не відсортована. Треба знайти варіант найбільшої (по кількості елементів) неспадаючої послідовності, складеної з чисел цього ряду. Порядок включення чисел у неспадаючу послідовність повинен відповідати порядку слідування чисел у початковій послідовності.
Приклад: Вхідні дані Результат
59 4
4 18
21 27
36 34
18 45
27 47
79 93
34
45
47
34
93
13. Задача про рюкзак. Суть задачі полягає в тому,що із 2n альтернативних об'єктів треба відібрати n об'єктів за таким принципом. Нехай є інформація про вагу і вартість кожного об'єкту, кількість об'єктів, які можна покласти в рюкзак і максимальна вага рюкзака. Побудувати дерево пошуку і знайти ньому розв'язок у вигляді максимально можливої ціни рюкзака із n об'єктів і ваги рюкзака, що є меншою за максимально допустиму вагу рюкзака. Метод пошуку з обмеженнями є вдосконаленням пошуку з поверненням, оскільки він не обстежує гілки, в яких вага набраних об'єктів є більшою за максимально допустиму вагу рюкзака.
14. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка розставить мінімальну кількість білих коней так, щоб пробивалися всі вільні позиції.
15. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка розставить мінімальну кількість білих ферзів так, щоб пробивалися всі вільні позиції.
16. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка розставить максимальну кількість білих коней так, щоб вони не били один одного.
17. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка розставить максимальну кількість білих ферзів так, щоб вони не били один одного.
18. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка знайде всі найкоротші маршрути коня між двома заданими позиціями.
19. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка знайде всі найкоротші маршрути ферзя між двома заданими позиціями.
20. Нехай задано шахове поле розміру N*N, у деяких позиціях якого розставлені чорні фігури. Написати програму, яка розставить мінімальну кількість білих коней так, щоб пробивалися всі вільні позиції не менше K раз.
5. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
Перша літера прізвища студента
День народження студента
Варіант
А, І, С
Б, Ї, Т
В, Й, У
Г, К, Ф
Д, Л, Х
Е, М, Ц
Є, Н, Ч
Ж,О,Ш,Щ
З, П, Ю
И, Р, Я
1, 11, 21
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
ІІ 11
ІІ 12
ІІ 13
ІІ 14
ІІ 15
ІІ 16
ІІ 17
ІІ 18
ІІ 19
ІІ 20
2, 12, 22
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 17
І 19
ІІ 2
ІІ 3
ІІ 4
ІІ 5
ІІ 6
ІІ 7
ІІ 8
ІІ 9
ІІ 10
ІІ 1
3, 13, 23
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
ІІ 3
ІІ 4
ІІ 5
ІІ 6
ІІ 7
ІІ 8
ІІ 9
ІІ 10
ІІ 1
ІІ 2
4, 14, 24
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 18
І 19
ІІ 11
ІІ 12
ІІ 13
ІІ 14
ІІ 15
ІІ 16
ІІ 17
ІІ 18
ІІ 19
ІІ 20
5, 15, 25
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
ІІ 5
ІІ 6
ІІ 7
ІІ 8
ІІ 9
ІІ 10
ІІ 1
ІІ 2
ІІ 3
ІІ 4
6, 16, 26
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 4
І 5
ІІ 17
ІІ 18
ІІ 19
ІІ 20
ІІ 11
ІІ 12
ІІ 13
ІІ 14
ІІ 15
ІІ 16
7, 17, 27
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
І 13
І 14
ІІ 8
ІІ 9
ІІ 10
ІІ 1
ІІ 2
ІІ 3
ІІ 4
ІІ 5
ІІ 6
ІІ 7
8, 18, 28
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
ІІ 9
ІІ 10
ІІ 1
ІІ 2
ІІ 3
ІІ 4
ІІ 5
ІІ 6
ІІ 7
ІІ 6
9, 19, 29
І 13
І 14
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
ІІ 10
ІІ 11
ІІ 12
ІІ 13
ІІ 14
ІІ 15
ІІ 16
ІІ 17
ІІ 18
ІІ 19
10, 20, 30
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
ІІ 1
ІІ 2
ІІ 3
ІІ 4
ІІ 5
ІІ 6
ІІ 7
ІІ 8
ІІ 9
ІІ 10
6. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та номер варіанту.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи.
2. Завдання 1.
2.1. Постановка задачі.
2.2. Словесний алгоритми розв’язання задачі.
2.3. Динаміка вмісту бінарного дерева.
2.4. Обхід дерева.
а) послідовність вершин дерева при проходженні його у прямому порядку;
б) послідовність листків дерева при проходженні його у зворотньому порядку;
в) послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
2.5. Результати виконання програми.
3. Завдання 2.
3.1. Постановка задачі.
3.2. Словесний алгоритми розв’язання задачі.
2.3. Система тестів зі схематичними зображеннями дерев
2.4. Результати виконання програми.
Висновки.
Додатоки (тексти програм з коментарями).
7. КОНТРОЛЬНІ ЗАВДАННЯ
1. Для заданого на Мал.1 бінарного дерева (БД) дайте відповіді на наступні питання:
Кількість вузлів БД.
Глибина БД.
Степінь БД.
Степінь вузла 6.
Рівень вузла 2.
Всі вузли 3 рівня.
Корінь БД .
Всі листки БД.
Всі вершини БД.
Безпосередні нащадки вузла 4.
Нащадки вузла 4.
Безпосередні предки вузла 6.
Предки вузла 8.
Батько вузла 2.
Сини вузла 4.
Брат вузла 6.
2. Запишіть послідовність вузлів при проходження БД :
у прямому порядку,
у симетричному порядку,
у зворотньому порядку.
3. Домалюйте це БД до найближчого строго БД.
4. Домалюйте це БД до найближчого повного БД.
5. Домалюйте це БД до найближчого майже повного строго БД.
6. Перемалюйте це БД після вилучення з нього вузла 4.
7. Для заданого на Мал.1 БД намалюйте його представлення на базі масиву розмірністю n=15.
8. Побудуйте бінарне дерево пошуку , згідно заданої послідовності.
5 , 1 , 8 , 3 , 8 , 9 , 6 , 0 , 7 , 1 , 4 , 6 , 2 , 0 , 1 , 7 , 9 , 5 .
СПИСОК ЛІТЕРАТУРИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином
28.02.2016 12:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора