НОУ ІНТУЇТ | лекція | Рекурсія і дерева

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

Лемма 5.2. Рекурсивний алгоритм "розділяй і володарюй" для завдання про Ханойські вежі дає рішення, що приводить до 2N - 1 переміщенням.

Як завжди, з коду негайно випливає, що кількість переміщень задовольняє умові рекурентності. В даному випадку рекуррентная формула схожа на формулу 2.5:

TN = 2TN -1 + 1, при , T1 = 1.

Вгаданий результат можна безпосередньо перевірити методом індукції: ми маємо T (1) = 21 - 1 = 1; і, якщо для до <N вірно T (к) = 2k - 1, то T (N) = 2 (2N -1 - 1) + 1 = 2N - 1.

Програма 5.7. Рішення завдання про Ханойські вежі

Щоб перемістити вежу з дисків вправо, ми переміщаємо (рекурсивно) все диски, крім нижнього, вліво, потім перекладаємо нижній диск вправо, а потім переміщаємо (рекурсивно) вежу поверх нижнього диска.

void hanoi (int N, int d) {if (N == 0) return; hanoi (N -1, -d); shift (N, d); hanoi (N -1, -d); }
Мал. 5.7. Ханойські вежі

На цій схемі показано рішення задачі про Ханойські вежі з п'ятьма дисками. Ми переміщаємо чотири верхніх диска вліво на одну позицію (лівий стовпець), потім перекладаємо диск 5 вправо, а потім верхні чотири диски перемещаем вліво на одну позицію (правий стовпець). Наведена нижче послідовність викликів функцій утворює обчислення для трьох дисків. Обчислена послідовність переміщень - +1 -2 +1 +3 +1 -2 +1 - з'являється в рішенні чотири рази (для прикладу показані перші сім переміщень).

Якщо монахи перекладають по одному диску в секунду, то для завершення роботи їм буде потрібно, щонайменше, 348 століть (див. Мал. 2.1 ) - зрозуміло, якщо вони не допускають помилок. Швидше за все, кінець світу настане навіть пізніше цього терміну, оскільки, по -видимому, ченці не користуються програмою 5.7 для швидкого з'ясування, який диск потрібно перекласти наступним. А тепер давайте проаналізуємо метод, який веде до простого (НЕ рекурсивному) рішенням, що спрощує прийняття рішення. Не хочеться допомагати монахам, однак цей метод має велике значення для безлічі практично важливих алгоритмів.

Щоб зрозуміти рішення задачі про Ханойські вежі, розглянемо просту задачу малювання міток на лінійці. Кожні 1/2 дюйма на лінійці відзначаються рискою, кожні 1/4 дюйма відзначаються кілька коротшими рисками, 1/8 дюйма - ще більш короткими і т.д. Завдання полягає в створенні програми для малювання цих міток для будь-якого заданого дозволу, за умови, що в нашому розпорядженні є процедура mark (x, h) для малювання мітки висотою h умовних одиниць в позиції x.

Якщо необхідний дозвіл дорівнює 1 / 2n дюйма, ми перейдемо до іншої задачі: помістити мітки в кожній точці в інтервалі від 0 до 2n, за винятком кінцевих точок. Тоді середня мітка повинна мати висоту n одиниць, мітки в середині лівої і правої половин повинні мати висоту n - 1 одиниць і т.д. Програма 5.8 - простий алгоритм "розділяй і володарюй" для виконання цього завдання; його робота на невеликому прикладі проілюстрована на Мал. 5.8 . Рекурсивний метод полягає в наступному. Для приміщення міток на інтервалі він спочатку ділиться на дві рівні половини. Потім створюються (рекурсивно) коротші мітки в лівій половині, в середині поміщається довга мітка, і створюються (рекурсивно) коротші мітки в правій половині. на Мал. 5.8 видно, що за допомогою цього методу мітки створюються по порядку, зліва направо (тобто итеративно) - і проблема полягає в обчисленні довжин міток. Дерево рекурсії, наведене на малюнку, допомагає зрозуміти обчислення: переглядаючи його зверху вниз, ми бачимо, що довжина міток зменшується на 1 для кожного рекурсивного виклику функції. Якщо переглядати дерево в поперечному напрямку, ми отримуємо мітки в порядку нанесення, оскільки для кожного даного вузла спочатку малюються мітки, пов'язані з викликом функції зліва, потім мітка, пов'язана з цим вузлом, а потім мітки, пов'язані з викликом функції праворуч.

Програма 5.8. Застосування алгоритму "розділяй і володарюй" для малювання лінійки

Для відтворення міток на лінійці ми малюємо мітки в лівій половині, потім найдовшу мітку в середині, а потім мітки в правій половині. Дана програма призначена для використання зі значенням r - l, рівним ступеня 2 - і це властивість зберігається в її рекурсивних викликах (див. Вправу 5.27).

void rule (int l, int r, int h) {int m = (l + r) / 2; if (h> 0) {rule (l, m, h -1); mark (m, h); rule (m, r, h -1); }}

Відразу видно, що послідовність довжин в точності збігається з послідовністю переміщуються дисків при вирішенні задачі про Ханойські вежі. Дійсно, простим доказом їх ідентичності є ідентичність рекурсивних програм. Тобто для визначення перекладають диска наші монахи могли б скористатися мітками на лінійці.

Більш того, і рішення задачі про Ханойські вежі в програмі 5.7, і програма малювання лінійки в програмі 5.8 є варіантами загальної схеми "розділяй і володарюй", представленої програмою 5.6. Всі три програми вирішують завдання розміру 2n, розбиваючи її на два завдання розміру 2n -1. При знаходженні максимуму час отримання рішення лінійно залежить від розміру вхідного масиву; при малюванні лінійки і при вирішенні задачі про Ханойські вежі час лінійно залежить від розміру вихідного масиву. Зазвичай вважається, що час виконання завдання про Ханойські вежі експоненціально, хоча обсяг завдання вимірюється кількістю дисків, тобто п.

Виклики функції, які малюють мітки на лінійці

Ця послідовність викликів функції обчислює довжини міток для малювання лінійки довжиною 8, в результаті чого наносяться мітки 1, 2, 1, 3, 1, 2 і 1.

Малювання міток на лінійці за допомогою рекурсивної програми не представляє особливої ​​складності, але, може бути, існує більш простий спосіб обчислення довжини i -ої позначки для будь-якого даного значення i? на Мал. 5.9 показаний ще один простий обчислювальний процес, що дає відповідь на це питання. Виявляється, i-е число, що виводиться і програмою рішення задачі про Ханойські вежі, і програмою малювання лінійки - просто кількість кінцевих нульових розрядів в двійковому поданні i. Це твердження можна довести методом індукції по відповідності з формулюванням методу "розділяй і володарюй" для процесу виведення таблиці "розрядних чисел: досить надрукувати таблицю (п - 1) розрядних чисел, кожному з яких передує 0, а потім надрукувати таблицю (п - 1) розрядних чисел, кожному з яких передує 1 (див. вправу 5.25).

Стосовно до задачі про Ханойські вежі відповідність n-розрядних чисел дає простий алгоритм вирішення задачі. Можна перемістити стопку дисків на один стрижень вправо, повторюючи до завершення наступні два кроки:

• Переміщення маленького диска вправо, якщо п непарній (вліво, якщо парне).
• Виконання єдиного дозволеного переміщення, що не зачіпає маленький диск.

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

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

Формальне доказ методом індукції того, що в рішенні задачі про Ханойські вежі кожне друге переміщення є перекладанням маленького диска (їм же все починається і закінчується), дуже повчально: Для n = 1 існує тільки одне переміщення, що зачіпає маленький диск, отже, твердження підтверджується. При n> 1 з припущення, що твердження справедливе для n - 1, слід його справедливість і для n: перше рішення для n - 1 починається перекладанням маленького диска, а друге рішення для n - 1 завершується перекладанням маленького диска - отже, рішення для n починається і завершується перекладанням маленького диска. Переміщення, що не зачіпає маленький диск, вставляється між двома переміщеннями, які його зачіпають (перекладанням, завершальним перше рішення для n - 1, і перекладанням, початківцям друге рішення для n - 1) - отже, властивість, що кожне друге переміщення є перекладанням маленького диска , залишається в силі.

Мал.5.9.

Двійковий підрахунок і функція малювання лінійки

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

Програма 5.9 - альтернативний спосіб малювання лінійки, на який наштовхнуло відповідність з двійковими числами (див. Мал. 5.10 ). Цю версію алгоритму називають висхідною (bottom -up) реалізацією. Вона не є рекурсивної, але безумовно навіяна рекурсивним алгоритмом. Цей зв'язок між алгоритмами "розділяй і володарюй" і двійковими уявленнями чисел часто допомагає знайти рішення при аналізі і розробці вдосконалених версій, таких як висхідні підходи. Ми будемо розглядати дану можливість, щоб зрозуміти і, можливо, удосконалити кожен розглянутий алгоритм виду "розділяй і володарюй".

Висхідний підхід передбачає зміну порядку виконання обчислень при малюванні лінійки. на Мал. 5.11 показаний ще один приклад, в якому змінено порядок проходження трьох викликів функцій в рекурсивної реалізації. Цей приклад відповідає рекурсивному малювання спочатку описаним способом: нанесення середньої мітки, потім лівої половини, а потім правою. Послідовність нанесення міток виглядає складною, але є результатом простої перестановки двох операторів в програмі 5.8. Як буде показано в розділі 5.6, взаємозв'язок між Мал. 5.8 і Мал. 5.11 те саме відмінності між Постфіксний і префіксними арифметичними виразами.

Програма 5.9. Нерекурсівние програма для малювання лінійки

На відміну від програми 5.8, лінійку можна намалювати, спочатку зобразивши всі мітки довжиною 1, потім все мітки довжиною 2 і т.д. Мінлива t представляє довжину міток, а змінна j - кількість позначок між двома послідовними мітками довжиною t. Зовнішній цикл for збільшує значення t при збереженні співвідношення j = 2 -1. Внутрішній цикл for малює все мітки довжиною t.

void rule (int l, int r, int h) {for (int t = 1, j = 1; t <= h; j + = j, t ++) for (int i = 0; l + j + i <= r; i + = j + j) mark (l + j + i, t); }

Можливо, нанесення міток в порядку, показаному на Мал. 5.8 , Більш зручно в порівнянні з обчисленнями в зміненому порядку, які містяться в програмі 5.9 і наведені на Мал. 5.11 , Оскільки в цьому випадку можна намалювати лінійку довільної довжини. Досить уявити собі графічний пристрій, яке просто безперервно переміщається від однієї мітки до наступної. Аналогічно, при вирішенні задачі про Ханойські вежі ми обмежені послідовністю переміщень, яка повинна бути виконана. Взагалі кажучи, багато рекурсивні програми ґрунтуються на рішеннях підзадач, які повинні бути виконані в конкретному порядку. Для інших обчислень (див., Наприклад, програму 5.6) порядок вирішення підзадач ролі не грає. Для таких обчислень єдиним обмеженням є необхідність вирішення підзадач перед тим, як можна буде вирішити головну задачу. Розуміння того, коли можна змінювати порядок обчислення, не тільки служить ключем до успішної розробки алгоритму, але і в багатьох випадках безпосередньо практичний вплив. Наприклад, це питання виключно важливий при реалізації алгоритмів для роботи на паралельних процесорах.

Висхідний підхід відповідає загальному методу розробки алгоритмів, при якому задача вирішується шляхом вирішення спочатку елементарних підзадач з подальшим об'єднанням цих рішень для отримання рішення кілька великих подзадач і т.д., поки вся задача не буде вирішена. Цей підхід можна було б назвати "об'єднуй і володарюй".

Лише незначний крок відокремлює малювання лінійок від малювання двовимірних візерунків, схожих на показаний на Мал. 5.12 . Цей малюнок показує, як просте рекурсивне опис може призводити до складних на вигляд обчислень (див. Вправу 5.30).

Малювання лінійки в висхідному порядку

Для малювання лінійки нерекурсівние методом спочатку малюються всі мітки довжиною 1 і пропускаються позиції, потім малюються мітки довжиною 2 і пропускаються залишаються позиції, потім малюються мітки довжиною 3 з пропуском залишаються позицій і т.д.

Виклики функцій для малювання лінійки (версія з використанням прямого обходу)

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

Двовимірна фрактальная зірка

Цей фрактал - двовимірна версія Мал. 5.10 . Окреслені квадрати на нижньому малюнку демонструють рекурсивную структуру обчислення.

Рекурсивно певні геометричні візерунки, на зразок показаного на Мал. 5.12 , Іноді називають фракталами. При використанні більш складних примітивів малювання і більш складних рекурсивних функцій (особливо рекурсивно певних функцій на дійсній осі та комплексної площині) можна отримати разюче різноманітні і складні візерунки. на Мал. 5.13 наведено ще один приклад - зірка Коха, яка визначається рекурсивно наступним чином: зірка Коха порядку 0 - простий виступ, показаний на Мал. 4.3 , А зірка Коха n -го порядку - це зірка Коха порядку п - 1, в якій кожен відрізок замінений зіркою порядку 0 відповідного розміру.

Подібнорішенням завдань малювання лінійки і Ханойські веж, ці алгоритми лінійні по відношенню до кількості кроків, але ця кількість пов'язано експоненційної залежністю з максимальною глибиною рекурсії (див. Вправи 5.29 і 5.33). Вони також можуть бути безпосередньо пов'язані з послідовністю натуральних чисел у відповідній системі числення (див. Вправу 5.34).

Рекурсивна PostScript -програма для малювання фрактала Коха

Ця зміна програми PostScript, наведеної на Мал. 4.3 , Перетворює результат її роботи в фрактал (див. Текст).

Завдання про Ханойські вежі, малювання лінійки і фрактали вельми цікаві, а зв'язок з двійковим числами вражає, проте всі ці питання цікавлять нас перш за все тому, що полегшують розуміння одного з основних методів розробки алгоритмів - поділ завдання навпіл і незалежне рішення однієї або обох половин завдання . Можливо, це найбільш важлива з усіх технологій, що розглядаються в книзі. В таблиця 5.1 детально описані бінарний пошук і сортування злиттям, які не тільки є важливими і широко використовуваними на практиці алгоритмами, але і служать типовими прикладами розробки алгоритмів виду "розділяй і володарюй".

Бінарний пошук (див. "Принципи аналізу алгоритмів" і "Таблиці символів і дерева бінарного пошуку" ) І сортування злиттям (див. "Злиття і сортування злиттям" ) - типові алгоритми "розділяй і володарюй", які забезпечують гарантовану оптимальну продуктивність, відповідно, пошуку і сортування. Рекурентні співвідношення демонструють сутність обчислень методом "розділяй і володарюй" для кожного алгоритму. (Висновок рішень, наведених у правій колонці, см. В розділах 2.5 "Принципи аналізу алгоритмів" і 2.6.) При бінарному пошуку задача ділиться навпіл, виконується одне порівняння, а потім рекурсивний виклик для однієї з половин. При сортуванні злиттям завдання ділиться навпіл, потім виконується рекурсивна обробка обох половин, після чого програма виконує N порівнянь. У книзі буде розглянуто безліч інших алгоритмів, розроблених із застосуванням цих рекурсивних схем.

Таблиця 5.1. Основні алгоритми типу "розділяй і володарюй" рекурентне співвідношення наближене рішення Бінарний пошук кількість порівнянь CN = CN / 2 + 1 lg N Сортування злиттям кількість рекурсивних викликів AN = 2AN / 2 + 1 N кількість порівнянь CN = 2CN / 2 + N NlgN

Швидке сортування (див. "Швидке сортування" ) І пошук в бінарному дереві (див. "Таблиці символів і дерева бінарного пошуку" ) Представляють важливу різновид базового підходу "розділяй і володарюй", в якій завдання розбивається на підзадачі розмірів k - 1 і N - k для деякого k, визначеного у вхідних даних. При випадкових вхідних даних ці алгоритми розбивають завдання на підзадачі, розміри яких в середньому вдвічі менше вихідного (як в сортуванні злиттям або бінарному пошуку). Вплив цієї відмінності буде розглянуто при вивченні цих алгоритмів.

Заслуговують на увагу і такі різновиди основної теми: розбиття на частини різних розмірів, розбиття більш ніж на дві частини, розбиття на перекриваються частини і виконання різного обсягу обчислень в нерекурсивною частини алгоритму. У загальному випадку алгоритми "розділяй і володарюй" вимагають виконання обчислень для розбиття вхідного масиву на частини, або для об'єднання результатів обробки двох незалежно вирішених частин вихідної задачі, або для спрощення завдання після того як половина вхідного масиву оброблена. Тобто, код може знаходитися перед, після і між двома рекурсивними викликами. Природно, подібні варіації призводять до створення більш складних алгоритмів, ніж бінарний пошук або сортування злиттям, і ці алгоритми важче аналізувати. У даній книзі будуть розглянуті численні приклади; до більш складним додаткам і способам аналізу ми повернемося в частині VIII.

вправи

5.16. Напишіть рекурсивну програму, яка знаходить максимальний елемент в масиві, виконуючи порівняння першого елемента з максимальним елементом іншої частини масиву (знайденим рекурсивно).

5.17. Напишіть рекурсивну програму, яка знаходить максимальний елемент в зв'язковому списку.

5.18 Змініть програму "розділяй і володарюй" для відшукання максимального елемента в масиві (програма 5.6), щоб вона ділила масив розміру N на дві частини, одна з яких має розмір k = 2risN - 1, а друга - N - до (щоб розмір хоча б однієї частини був ступенем 2).

5.19. Намалюйте дерево, яке відповідає рекурсивним викликам, виконуваних програмою з вправи 5.18 при розмірі масиву 11.

5.20. Методом індукції доведіть, що кількість викликів функції, які виконуються будь-яким алгоритмом "розділяй і володарюй", який ділить завдання на частини, в сумі становлять завдання в цілому, а потім вирішує частини рекурсивно, лінійно щодо розміру завдання.

5.21. Доведіть, що рекурсивне рішення задачі про Ханойські вежі (програма 5.7) є оптимальним. Тобто покажіть, що будь-яке рішення вимагає щонайменше 2N - 1 перекладань.

5.22. Напишіть рекурсивну програму, яка обчислює довжину i -ої позначки на лінійці з 2n - 1 мітками.

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

5.24. Напишіть програму, яка видає рішення задачі про Ханойські вежі шляхом заповнення масиву, що містить всі переміщення, як зроблено в програмі 5.9.

5.25. Напишіть рекурсивну програму, яка заповнює масив розміром n х 2n нулями і одиницями таким чином, щоб масив представляв все n-розрядні числа, як показано на Мал. 5.9 .

5.26. Наведіть результати використання рекурсивної програми малювання лінійки (програма 5.8) для наступних значень аргументів: rule (0, 11, 4), rule (4, 20, 4) і rule (7, 30, 5).

5.27. Доведіть наступне властивість програми малювання лінійки (програма 5.8): якщо різниця між її першими двома аргументами є ступенем 2, то обидва її рекурсивних виклику також володіють цією властивістю.

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

5.29. Скільки квадратів зображено на Мал. 5.12 (Включаючи і ті, які приховані великими квадратами)?

5.30. Напишіть рекурсивну програму на C ++, результатом якої буде PostScript -програма в формі списку викликів функцій xyr box, яка викреслює нижню діаграму на Мал. 5.12 ; функція box малює квадрат rxr в точці з координатами (x, y). Реалізуйте функцію box у вигляді команд PostScript (див. "Абстрактні типи даних" ).

5.31. Напишіть висхідну нерекурсівние програму (аналогічну програму 5.9), яка викреслює верхню частину Мал. 5.12 способом, описаним у вправі 5.30.

5.32. Напишіть PostScript -програма, викреслюють нижню частину Мал. 5.12 .

5.33. Скільки прямолінійних відрізків містить зірка Коха "-го порядку?

5.34. Креслення зірки Коха n -го порядку зводиться до виконання послідовності команд виду "повернути на а градусів, потім прокреслити відрізок довжиною 1/3" ". Знайдіть зв'язок з системами числення, яка дозволяє викреслити зірку шляхом збільшення значення лічильника і подальшого обчислення кута а з цього значення.

5.35. Змініть програму малювання зірки Коха, наведену на Мал. 5.13 , Для створення іншого фрактала, на основі фігури, що складається з 5 ліній нульового порядку, що викреслюються зсувами на одну умовну одиницю в східному, північному, східному, південному і східному напрямках (див. Мал. 4.3 ).

5.36. Напишіть рекурсивну функцію "розділяй і володарюй" для відображення апроксимації прямолінійного відрізка в просторі цілочисельних координат для заданих кінцевих точок. Вважайте, що всі координати мають значення від 0 до M. Рада: спочатку поставте крапку поблизу середини сегмента.