Ім'я файлу: Рекурсія - укр.doc
Розширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
Розширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
Алгоритм 3: Сортування деревом (tree sort).
Перш ніж переходити до пояснення суті алгоритму введемо одне поняття. Двійковим деревом пошуку називається бінарне дерево, в вузлах якого розташовуються числа таким чином, що в лівому поддереве кожного вузла знаходяться числа менші, ніж в цьому вузлі, а в правому поддереве більше або рівні того, що в цьому вузлі. На рис. 10 показано два приклади дерев пошуку, складених з одних і тих же чисел.
Рис. 10. Двійкові дерева пошуку, складені з чисел 1, 3, 4, 6, 7, 8, 10, 13, 14.
Якщо для кожної вершини висота піддерев розрізняється не більше ніж на одиницю, то дерево називається збалансованим . Збалансовані дерева пошуку також називаються АВЛ-деревами (за першими літерами прізвищ винахідників Г. М. Адельсона-Бєльського і Е. М. Ландіса). Як видно на рис. 10а показано збалансоване дерево, на рис. 10б незбалансоване.
Зауважимо, що розташування чисел по зростанню вийде, якщо обходити ці дерева в зворотному прядки.
Сортування деревом вийде, якщо ми спочатку послідовно будемо додавати числа з масиву в двійкове дерево пошуку, а потім обійдемо його в зворотному порядку.
Якщо дерево буде близько до збалансованого, то сортування зажадає приблизно n log 2 n операцій. Якщо не пощастить і дерево виявиться максимально незбалансованим, то сортування займе n 2 операцій.
6.5. Довільна кількість вкладених циклів
Розмістивши рекурсивні виклики всередині циклу, по суті, отримаємо вкладені цикли, де рівень вкладеності дорівнює глибині рекурсії.
Для прикладу напишемо процедуру, що друкує всі можливі поєднання з k чисел від 1 до n (
). Числа, що входять в кожне поєднання, будемо друкувати в порядку зростання. Сполучення з двох чисел ( k = 2) друкуються так:| 1 2 3 | for i1: = 1 to n do for i2: = i1 + 1 to n do writeln (i1, '', i2); |
Сполучення з трьох чисел ( k = 3) так:
| 1 2 3 4 | for i1: = 1 to n do for i2: = i1 + 1 to n do for i3: = i2 + 1 to n do writeln (i1, '', i2, '', i3); |
Однак, якщо кількість чисел в поєднанні задається змінною, то доведеться вдатися до рекурсії.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | procedure Combinations ( n, k: integer; // Масив, в якому будемо формувати поєднання var Indexes: array of integer; // Лічильник глибини рекурсії d: integer); var i, i_min: integer; s: string; begin if d begin if d = 0 then i_min: = 1 else i_min: = Indexes [d-1] + 1; for i: = i_min to n do begin Indexes [d]: = i; Combinations (n, k, Indexes, d + 1); end; end else begin for i: = 0 to k-1 do write (Indexes [i], ''); writeln; end; end; |
6.6. Завдання на графах
Графом називають графічне зображення, що складається з вершин ( вузлів ) і з'єднують деякі пари вершин ребер (рис. 11а).
Більш строго: граф - сукупність безлічі вершин і безлічі ребер. Безліч ребер - підмножина евклідового квадрата безлічі вершин (тобто ребро з'єднує рівно дві вершини).
Ребрах можна також привласнити напрямок. Граф в цьому випадку називається оріетірованним (рис. 11б).
Рис. 11. (а) Граф. (Б) Орієнтований граф.
Теорія графів знаходить застосування в самих різних областях. Кілька прикладів:
Логістика та транспортні системи. Вершинами будуть склади з товарами або пункти призначення, а ребра - дороги, їх з'єднують.
Маршрутизація мереж. Вершини - комп'ютери, з'єднані в мережу, ребра - зв'язки між ними. Вирішується задача про шляхи передачі даних з одного комп'ютера на інший.
Комп'ютерна хімія. Моделі у вигляді графів використовуються для опису шляхів протікання складних реакцій. Вершини - беруть участь в реакціях речовини, ребра - шляхи перетворень речовин. Також графом є зображення структур молекул: вершини - атоми, ребра - хімічні зв'язки.
Електричні сітки.
Сайти в Інтернеті можна вважати вузлами орієнтованого графа, ребрами якого будуть гіперпосилання.
І т.д.
Сучасна теорія графів є потужною формальну систему, що має неозоре безліч застосувань.
Шляхом або ланцюгом в графі називається послідовність вершин, в якій кожна вершина з'єднана ребром з наступною. Шляхи, в яких початкова і кінцева вершина збігаються, називають циклами . Якщо для кожної пари вершин існує шлях їх з'єднують, то такий граф називають зв'язковим .
У програмуванні використовуються три способи зберігання в пам'яті інформації про стуктуре графів.
1) Матриці суміжності
Квадратна матриця M, де як рядки, так і стовпці відповідають вершинам графа. Якщо вершини з номерами i та j з'єднані ребром, то M ij = 1, інакше M ij = 0. Для неорієнтованого графа матриця, очевидно, симетрична. Орієнтований граф задається антисиметричною матрицею. Якщо ребро виходить з вузла i і приходить у вузол j , то M ij = 1, а симетричний елемент M ji = -1.
2) Матриця інцидентності
Стовпці матриці відповідають вершинам, а рядки ребрах. Якщо ребро з номером i з'єднує вершини з номерами j і k , то елементи матриці I ij = I ik = 1. Інші елементи i -го рядка рівні 0.
3) Список ребер
Просто набір пар номерів вершин, з'єднаних ребрами.
Розглянуті вище дерева є окремим випадком графів. Деревом буде будь-який зв'язний граф, що не містить циклів.
Завдання, що виникають в теорії графів численні і різноманітні. Про них пишуться товсті книги, і немає ніякої можливості скільки-небудь повно їх тут оглянути. Тому ми обмежимося зауваженням, що багато хто з цих завдань вимагають систематичного перебору вершин. Якщо перебирати вершини, пов'язані ребрами і при цьому відвідувати кожну вершину тільки один раз, то безліч відвідуваних алгоритмом вершин буде утворювати дерево, а сам алгоритм природно зробити рекурсивним.
Наприклад, класичної завданням є пошук шляху з однієї вершини в іншу. Алгоритм пошуку повинен буде побудувати дерево можливих шляхів з початкової вершини, кінцевими вузлами якого будуть вершини, з яких не можна потрапити ні в яку вершину, що не належить раніше побудованої гілки (НЕ позначену як уже відвідану). Завдання буде вирішена, коли один з кінцевих вузлів співпаде з кінцевою вершиною, шлях до якої потрібно знайти.
6.7. фрактали
Фракталами називають геометричні фігури, що володіють властивістю самоподібності, тобто складаються з частин, подібних до всієї фігури.
Класичним прикладом є крива Коха, побудова якої показано на рис. 12. Спочатку береться відрізок прямої (рис. 12а). Він ділиться на три частини, середня частина вилучається і замість неї будується кут (рис. 12б), сторони якого рівні довжині вилученого відрізка (тобто 1/3 від довжини вихідного відрізка). Така операція повторюється з кожним з вийшов 4-х відрізків (рис. 12в). І так далі (рис. 12г). Крива Коха виходить після нескінченного числа таких ітерацій. На практиці побудова можна припинити, коли розмір деталей виявиться менше дозволу екрану (рис. 12 д).
Рис. 12. Процес побудови кривої Коха.
Ще одним прикладом може служити деревце на рис. 6. Воно також містить частини, подібні всьому дереву в цілому, що робить його фракталом.
Фрактали, по суті, рекурсивні структури і їх побудова природно виробляти за допомогою рекурсивних процедур.
7. Позбавлення від рекурсії
Будь-рекурсивний алгоритм може бути переписаний без використання рекурсії. Зауважимо, що швидкодія алгоритмів при позбавленні від рекурсії, як правило, підвищується. Ще однією причиною щоб позбутися від рекурсії є обмеження на обсяг збережених програмою локальних змінних і значень параметрів одночасно виконуються процедур. При дуже глибокої рекурсії цей обсяг зростає, і програма перестає працювати, видаючи помилку «Stack overflow» (переповнення стека).
Так чому ж люди продовжують користуватися рекурсивними алгоритмами? Очевидно, тому що це простіше і природніше, ніж відповідні нерекурсівние рішення. Проте, знання про способи обійтися без рекурсії необхідно.
Нижче представлено кілька варіантів того, як це можна зробити.
7.1. Явне використання стека
Стеком називається структура даних, в якій додавання і вилучення даних відбувається з одного кінця, званого вершиною стека (рис. 13). Наочним чином стека може служити стос тарілок - додавати або забрати тарілки можна тільки зверху. Кожна тарілка відповідає елементу даних.
Рис. 13. Наочне уявлення стека. Push (проштовхування) - традиційна назва для операції додавання даних в стек, Pop (виштовхування) - традиційна назва для операції вилучення даних з стека.
Коли одна процедура або функція викликає іншу, то параметри першої процедури, а також місце, з якого її виконання має продовжитися після того як відпрацює викликана процедура (точка повернення), запам'ятовуються в так званому стеку викликів . Якщо викликана процедура в свою чергу чогось викликає, то її параметри і точка повернення також додаються в стек.
При рекурсивних викликах стек викликів зберігає ланцюжок з даних про одночасно працюючих процедурах. У всіх розвинених середовищах розробки цей ланцюжок разом з успішної реєстрації параметрами процедур можна переглянути під час налагодження. Відповідна команда зазвичай називається "Call Stack" (в Delphi їй відповідає поєднання клавіш Ctrl - Alt - S).
Універсальний спосіб позбутися від рекурсії - це самостійно запрограмувати ті дії зі стеком, які фактично відбуваються, коли ви використовуєте рекурсивні виклики. Покажемо, як це можна зробити, на прикладі двічі викликає себе рекурсивної процедури.
Для початку реалізуємо у вигляді класу стек, який зберігає параметри процедури:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | type // Запис для зберігання параметрів процедур Parameters = record // Відомості про опції end; // Стек зручно реалізувати за допомогою пов'язаних списків // ( http://www.tvd-home.ru/prog/16_4 ) PList = ^ List; List = record Data: Parameters; Next: PList; end; // Описаний одновсязанний список з'єднаємо з методами // додавання і видалення елементів і отримаємо стек. Stack = class private StackTop: PList; public // Додавання даних procedure Push (NewData: Parameters); // Витяг даних function Pop: Parameters; // Перевірка наявності даних function Empty: boolean; end; implementation // Додавання даних procedure Stack.Push (NewData: Parameters); var NewElement: PList; begin New (NewElement); NewElement ^ .Data: = NewData; NewElement ^ .Next: = StackTop; StackTop: = NewElement; end; // Витяг даних function Stack.Pop: Parameters; var PopedElement: PList; begin PopedElement: = StackTop; StackTop: = StackTop ^ .Next; Pop: = PopedElement ^ .Data; Dispose (PopedElement); end; // Перевірка наявності даних function Stack.Empty: boolean; begin Empty: = StackTop = nil; end; |
Розглянемо узагальнену рекурсивную процедуру з двома викликами самої себе.
| 1 2 3 4 5 6 7 8 9 10 11 | procedure Recurs (P1: Parameters); begin DoSomething (P1); if <умова> then begin P2: = F (P1); Recurs (P2); P3: = G (P1); Recurs (P3); end; end; |
У даній процедурі деякі дії (DoSomething) виконуються багато разів при різних значеннях параметрів. Нерекурсивний аналог повинен зберігати ці параметри в стек. Кожен рекурсивний виклик буде відповідати додаванню чергових параметрів в стек. Замість рекурсії з'являється цикл, який виконується, поки в стеці є необроблені параметри.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | procedure NonRecurs (P1: Parameters); var S: Stack; P: Parameters; begin S: = Stack.Create; S.Push (P1); while not S.Empty do begin P1: = S.Pop; DoSomething (P1); if <умова> then begin P3: = G (P1); S.Push (P3); P2: = F (P1); S.Push (P2); end; end; end; |
Зверніть увагу, що рекурсивні виклики йшли спочатку для параметрів P2, потім для P3. У нерекурсивною процедурі в стек відправляються спочатку параметри P3, а тільки потім P2. Це пов'язано з тим, що при рекурсивних викликах в стек, по суті, відправляється недовиконання частина процедури, яка в нашому випадку містить виклик Recurs (P3).
Згаданої вище перестановки можна уникнути, якщо замість стека використовувати чергу - структуру даних, де додавання і витяг елементів відбувається з різних кінців. Це буде деяким відступом від точної імітації процесів при рекурсивних викликах. Однак в даному прикладі це здається більш зручним: кожен рекурсивний виклик буде прямо замінюватися додаванням параметрів в чергу.
7.2. Запам'ятовування послідовності рекурсивних викликів
Як говорилося вище, рекурсивні виклики утворюють дерево, де кожен вузол відповідає викликом однієї процедури. Послідовність виконання цих процедур відповідає тому або іншому алгоритму обходу вузлів. Якщо потрібно багато разів обійти вузли одного і того ж дерева, то можна один раз обійти їх рекурсивно, запам'ятати кількість і послідовність вузлів, а потім, користуючись цією інформацією, обходити вузли вже нерекурсівние.
Наприклад, в розділі 6.3 обговорювалася завдання обчислення арифметичних виразів, заданих рядком. Може виникнути ситуація, коли один і той же вираз буде потрібно обчислити багато разів при різних значеннях змінної x . Синтаксичне дерево, яке потрібно обходити при таких обчисленнях, не залежить від x . Можна обійти його один раз, побудувавши при цьому масив, де кожен елемент буде відповідати вузлу дерева, а їх послідовність - порядку обходу. Повторні обчислення при новому x зажадають тільки нерекурсівние перебору елементів масиву.
Ще один приклад такого запам'ятовування в завданню про обчислення значень багатовимірних поліномів дивіться тут: http://tvd-home.ru/numerical/polynom .
Такий підхід не позбавляє нас від рекурсії повністю. Однак він дозволяє обмежитися тільки одним зверненням до рекурсивної процедури, що може бути досить, якщо мотивом є турбота про максимальної продуктивності.
1 2 3 4