Ім'я файлу: Рекурсія - укр.doc
Розширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
Розширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
Алгоритм обходу в прямому порядку:
Потрапити в корінь,
Пройти всі піддерева зліва на право в прямому порядку.
Даний алгоритм рекурсівен, так як проходження дерева містить проходження піддерев, а вони в свою чергу проходяться за тим же алгоритмом.
Зокрема для дерева на рис. 3 і 4 прямой обхід дає послідовність вузлів: A, B, C, D, E, F, G.
Що Виходить послідовність відповідає послідовному зліва направо перерахуванню вузлів при поданні дерева за допомогою вкладених дужок і в десятковій системі Дьюї, а також проходу зверху вниз при поданні у вигляді уступчатого списку.
При реалізації цього алгоритму на мові програмування потрапляння в корінь відповідає виконання процедурою або функцією деяких дій, а проходження піддерев - рекурсивним викликам самої себе. Зокрема для бінарного дерева (де з кожного вузла виходить не більше двох піддерев) відповідна процедура буде виглядати так:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Preorder Traversal - англійська назва для прямого порядку procedure PreorderTraversal ({Аргументи}); begin // Проходження кореня DoSomething ({Аргументи}); // Проходження лівого піддерева if {Існує ліве піддерево} then PreorderTransversal ({Аргументи 2}); // Проходження правого піддерева if {Існує праве піддерево} then PreorderTransversal ({Аргументи 3}); end; |
Тобто спочатку процедура виробляє всі дії, а тільки потім відбуваються все рекурсивні виклики.
Алгоритм обходу в зворотному порядку:
Пройти ліве піддерево,
Потрапити в корінь,
Пройти наступне за лівим поддерево.
Потрапити в корінь,
і т.д поки не буде пройдено крайнє праве піддерево.
Тобто проходяться все піддерева зліва на право, а повернення в корінь розташовується між цими проходженнями. Для дерева на рис. 3 і 4 це дає послідовність вузлів: B, A, D, C, E, G, F.
У відповідній рекурсивної процедури дії будуть розташовуватися в проміжках між рекурсивними викликами. Зокрема для бінарного дерева:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Inorder Traversal - англійська назва для зворотного порядку procedure InorderTraversal ({Аргументи}); begin // Проходження лівого піддерева if {Існує ліве піддерево} then InorderTraversal ({Аргументи 2}); // Проходження кореня DoSomething ({Аргументи}); // Проходження правого піддерева if {Існує праве піддерево} then InorderTraversal ({Аргументи 3}); end; |
Алгоритм обходу в кінцевому порядку:
Пройти всі піддерева зліва на право,
Потрапити в корінь.
Для дерева на рис. 3 і 4 це дасть послідовність вузлів: B, D, E, G, F, C, A.
У відповідній рекурсивної процедури дії будуть розташовуватися після рекурсивних викликів. Зокрема для бінарного дерева:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // Postorder Traversal - англійська назва для кінцевого порядку procedure PostorderTraversal ({Аргументи}); begin // Проходження лівого піддерева if {Існує ліве піддерево} then PostorderTraversal ({Аргументи 2}); // Проходження правого піддерева if {Існує праве піддерево} the n PostorderTraversal ({Аргументи 3}); // Проходження кореня DoSomething ({Аргументи}); end; |
5.3. Подання дерева в пам'яті комп'ютера
Якщо деяка інформація розташовується в вузлах дерева, то для її зберігання можна використовувати відповідну динамічну структуру даних. На Паскалі це робиться за допомогою змінної типу запис (record), що містить покажчики на піддерева того ж типу. Наприклад, бінарне дерево, де в кожному вузлі міститься ціле число можна зберегти за допомогою змінної типу PTree, який описаний нижче:
| 1 2 3 4 5 6 | type PTree = ^ TTree; TTree = record Inf: integer; LeftSubTree, RightSubTree: PTree; end; |
Кожен вузол має тип PTree. Це покажчик, тобто кожен вузол необхідно створювати, викликаючи для нього процедуру New. Якщо вузол є кінцевим, то його полях LeftSubTree і RightSubTree присвоюється значення nil . В іншому випадку вузли LeftSubTree і RightSubTree також створюються процедурою New.
Схематично одна така запис зображена на рис. 5.
Рис. 5. Схематичне зображення записи типу TTree. Запис має три поля: Inf - деяке число, LeftSubTree і RightSubTree - покажчики на записи того ж типу TTree.
Приклад дерева, складеного з таких записів, показаний на малюнку 6.
Рис. 6. Дерево, складене із записів типу TTree. Кожен запис зберігає число і два покажчика, які можуть містити або nil , або адреси інших записів того ж типу.
Якщо ви раніше не працювали зі структурами складаються із записів, які містять посилання на записи того ж типу, то рекомендуємо ознайомитися з матеріалом про рекурсивних структурах даних .
6. Приклади рекурсивних алгоритмів
6.1. малювання дерева
Розглянемо алгоритм малювання деревця, зображеного на рис. 6. Якщо кожну лінію вважати вузлом, то дане зображення цілком задовольняє визначенню дерева, яке у попередньому розділі.
Рис. 6. Деревце.
Рекурсивна процедура, очевидно повинна малювати одну лінію (ствол до першого розгалуження), а потім викликати сама себе для малювання двох піддерев. Піддерева відрізняються від що містить їх дерева координатами початкової точки, кутом повороту, довжиною ствола і кількістю що містяться в них розгалужень (на одне менше). Всі ці відмінності слід зробити параметрами рекурсивної процедури.
Приклад такої процедури, написаний на Delphi, представлений нижче:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | procedure Tree ( Canvas: TCanvas; // Canvas, на якому буде малюватися дерево x, y: extended; // Координати кореня Angle: extended; // Кут, під яким росте дерево TrunkLength: extended; // Довжина стовбура n: integer // Кількість розгалужень (скільки ще належить // рекурсивних викликів) ); var x2, y2: extended; // Кінець ствола (точка розгалуження) begin x2: = x + TrunkLeng th * cos (Angle); y2: = y - TrunkLength * sin (Angle); Canvas.MoveTo (round (x), round (y)); Canvas.LineTo (round (x2), round (y2)); if n> 1 then begin Tree (Canvas, x2, y2, Angle + Pi / 4, 0.55 * TrunkLength, n-1); Tree (Canvas, x2, y2, Angle-Pi / 4, 0.55 * TrunkLength, n-1); end; end; |
Для отримання рис. 6 ця процедура була викликана з наступними параметрами:
| 1 | Tree (Image1.Canvas, 175, 325, Pi / 2, 120, 15); |
Зауважимо, що малювання здійснюється до рекурсивних викликів, тобто дерево малюється в прямому порядку.
6.2. Ханойські вежі
Згідно з легендою в Великому храмі міста Бенарас, під собором, який зазначає середину світу, знаходиться бронзовий диск, на якому укріплені 3 алмазних стержня, висотою в один лікоть і товщиною з бджолу. Давним-давно, на самому початку часів ченці цього монастиря завинили перед богом Брамою. Розгніваний, Брама спорудив три високих стрижня і на один з них помістив 64 диска з чистого золота, причому так, що кожен менший диск лежить на більшій. Як тільки всі 64 диска будуть перекладені зі стрижня, на який Бог Брама склав їх при створенні світу, на інший стрижень, вежа разом з храмом звернуться в пил і під грім загине світ.
У процесі потрібно, щоб більший диск жодного разу не опинявся над меншим. Ченці в скруті, в який же послідовності варто робити перекладання? Потрібно забезпечити їх софтом для розрахунку цієї послідовності.
Незалежно від Брами дану головоломку в кінці 19 століття запропонував французький математик Едуард Люка. У продається варіанті зазвичай використовувалося 7-8 дисків (рис. 7).
Рис. 7. Головоломка «Ханойські вежі».
Припустимо, що існує рішення для n -1 диска. Тоді для перекладання n дисків треба діяти наступним чином:
1) Перекладаємо n -1 диск. 2) Перекладаємо n -й диск на що залишився вільним штир. 3) Перекладаємо стопку з n -1 диска, отриману в пункті (1) поверх n -го диска.
Оскільки для випадку n = 1 алгоритм перекладання очевидний, то по індукції за допомогою виконання дій (1) - (3) можемо перекласти будь-яку кількість дисків.
Створимо рекурсивную процедуру, що друкує всю послідовність перекладань для заданої кількості дисків. Така процедура при кожному своєму виклик повинна друкувати інформацію про один перекладанні (з пункту 2 алгоритму). Для перекладань з пунктів (1) і (3) процедура викличе сама себе зі зменшеним на одиницю кількістю дисків.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | // n - кількість дисків // a, b, c - номера штирьків. Перекладання проводиться з штирька a, // на стрижень b при допоміжному штирьком c. procedur e Hanoi (n, a, b, c: integer); begin if n> 1 then begin Hanoi (n-1, a, c, b); writeln (a, '->', b); Hanoi (n-1, c, b, a); end else writeln (a, '->', b); end; |
Зауважимо, що безліч рекурсивно викликаних процедур в даному випадку утворює дерево, прохідне в зворотному порядку.
6.3. Синтаксичний аналіз арифметичних виразів
Завдання синтаксичного аналізу полягає в тому, щоб за наявною рядку, що містить арифметичний вираз, і відомими значеннями, що входять в неї змінних, обчислити значення виразу.
Процес обчислення арифметичних виразів можна представити у вигляді бінарного дерева. Дійсно, кожен з арифметичних операторів (+, -, *, /) вимагає двох операндів, які також будуть арифметичними виразами і, відповідно можуть розглядатися як піддерева. Рис. 8 показує приклад дерева, відповідного виразу:
Рис. 8. Синтаксичне дерево, відповідне арифметичному вираженню (6).
В такому дереві кінцевими вузлами завжди будуть змінні (тут x ) або числові константи, а всі внутрішні вузли будуть містити арифметичні оператори. Щоб виконати оператор, треба спочатку обчислити його операнди. Таким чином, дерево на малюнку слід обходити в кінцевому порядку. Відповідна послідовність вузлів
називається зворотної польської записом арифметичного виразу.
При побудові синтаксичного дерева слід звернути увагу на таку особливість. Якщо є, наприклад, вираз
і операції додавання і віднімання ми будемо зчитувати зліва на право, то правильне синтаксичне дерево буде містити мінус замість плюса (рис. 9а). По суті, це дерево відповідає вираженню Полегшити складання дерева можна, якщо аналізувати вираз (8) навпаки, справа наліво. В цьому випадку виходить дерево з рис. 9б, еквівалентну дереву 8а, але яке не потребує заміни знаків.
Аналогічно справа наліво потрібно аналізувати вирази, що містять оператори множення і ділення.
Рис. 9. Синтаксичні дерева для вираження a - b + c при читанні зліва направо (а) і справа наліво (б).
У файлі SynAn.pas наведено приклад функції, що обчислює значення виразів, що містять тільки одну змінну x . Дамо короткий опис реалізованого там алгоритму:
Обчислює вираз функція (CalcExpression) знаходить в рядку всі знаки «+» і «-», що не укладені в дужки. Ці знаки розбивають вираз на частини, що містять (поза дужками) тільки операції множення і ділення. Для обчислення значень цих частин викликається функція CalcMultDiv.
Функція CalcMultDiv знаходить в рядку всі знаки «*» і «/», що не укладені в дужки. Ці знаки розбивають вираз на частини, що містять числові константи, змінну x або виразу в дужках. Для обчислення значень цих частин викликається функція CalcValuesOrOpenParentheses.
Функція CalcValuesOrOpenParentheses визначає тип потрапив їй на вхід вираження. Якщо це числова константа або змінна x , то вона повертає їх значення. Якщо цей вислів в дужках, то для його обчислення рекурсивно викликається процедура CalcExpression.
Зауважимо, що в даному прикладі обчислення проводяться одночасно з аналізом строкового вираження. Це призводить до того, що для деяких виразів обчислення можуть відбуватися в 100 - 1000 разів повільніше, ніж, якби ці вирази були скомпільовані як частина програми. Якщо один і той же вираз потрібно обчислити багато разів при різних значення змінних, то слід розділити аналіз рядки і обчислення. Такий підхід може дозволити прискорити обчислення в сотні разів.
Результатом аналізу рядка повинна бути послідовність вузлів дерева в кінцевому порядку. Кожен вузол повинен зберігати інформацію про Підвузли і про ту операції, яка в ньому відбувається. Наприклад, вузли можна реалізувати у вигляді записів, одне з полів який має процедурний тип. Інший варіант - кожен вузол це об'єкт, де операція реалізована як віртуальний метод.
6.4. Швидкі сортування
Прості методи сортування на кшталт методу вибору або методу бульбашки сортують масив з n елементів за O ( n 2 ) операцій. Однак за допомогою принципу «розділяй і володарюй» вдається побудувати більш швидкі, що працюють за O ( n log 2 n ) алгоритми. Суть цього принципу в тому, що рішення виходить шляхом рекурсивного поділу завдання на кілька прості підзадачі того ж типу до тих пір, поки вони не стануть елементарними. Наведемо як приклади кілька швидких алгоритмів такого роду.
Алгоритм 1: «Швидка» сортування (quicksort).
1. Вибирається опорний елемент (наприклад, перший або випадковий).
2. реорганізовуючи масив так, щоб спочатку йшли елементи менші опорного, потім рівні йому, потім великі. Для цього достатньо пам'ятати, скільки було знайдено менших ( m 1 ) і великих ( m 2 ), ніж опорний і ставити черговий елемент на місце з індексом m 1 , а черговий більший на місце з індексом n -1- m 2 .
Після виконання такої операції опорний елемент і рівні йому стоять на своєму місці, їх переставляти більше не доведеться. Між «меншою» і «більшої» частина масиву перестановок також бути не може. Тобто ці частини можна сортувати незалежно один від одного.
3. Якщо «менша» або «велика» частина складається з одного елемента, то вона вже відсортована і робити нічого не треба. Інакше сортуємо ці частини за допомогою алгоритму швидкого сортування (тобто, виконуємо для неї кроки 1-3).
Як бачите, швидке сортування складається з виконання кроків 1 і 2 та рекурсивного виклику алгоритму для одержані частин масиву.
Алгоритм 2: Сортування злиттям (merge sort).
Ділимо масив на дві частини приблизно однакового розміру і, якщо вийшла половина масиву містить більше одного елемента, то сортуємо її за допомогою сортування злиттям. Як бачите, цей пункт містить рекурсивне звернення до всього алгоритму в цілому.
З'єднуємо дві відсортовані половини так, щоб вийшов один відсортований масив. Для цього поміщаємо в допоміжний масив елементи з першої половини, поки вони не перевершують чергового елемента з другої половини. Потім починаємо поміщати туди елементи другої половини, поки вони не перевершують чергового елемента з першої половини. Потім знову беремо елементи першої половини і т.д. Ця операція називається злиттям і вимагає стільки кроків, скільки елементів в обох з'єднуються масивах.
1 2 3 4