Ім'я файлу: Рекурсія - укр.doc
Розширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
7.3. Визначення вузла дерева по його номеруРозширення: doc
Розмір: 544кб.
Дата: 04.03.2020
скачати
Пов'язані файли:
МОДЕЛІ ДАНИХ.ppt
Ідея даного підходу в тому, щоб замінити рекурсивні виклики простим циклом, який виконається стільки раз, скільки вузлів в дереві, утвореному рекурсивними процедурами. Що саме буде робитися на кожному кроці, слід визначити за номером кроку. Зіставити номер кроку і необхідні дії - завдання не тривіальна і в кожному випадку її доведеться вирішувати окремо.
Наприклад, нехай потрібно виконати k вкладених циклів по n кроків в кожному:
| 1 2 3 4 | for i1: = 0 to n-1 do for i2: = 0 to n-1 do for i3: = 0 to n-1 do ... |
Якщо k заздалегідь невідомо, то написати їх явно, як показано вище неможливо. Використовуючи прийом, продемонстрований в розділі 6.5 можна отримати необхідну кількість вкладених циклів за допомогою рекурсивної процедури:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | procedure NestedCycles (Indexes: array of integer; n, k, depth: integer); var i: integer; begin if depth <= k then for i: = 0 to n-1 do begin Indexes [depth]: = i; NestedCycles (Indexes, n, k, depth + 1); end else DoSomething (Indexes); end; |
Щоб позбутися від рекурсії і звести все до одного циклу, звернемо увагу, що якщо нумерувати кроки в системі числення з основою n , то кожен крок має номер, що складається з цифр i1, i2, i3, ... або відповідних значень з масиву Indexes. Тобто цифри відповідають значенням лічильників циклів. Номер кроку в звичайній десятковій системі числення:
Всього кроків буде n k . Перебравши їх номери в десятковій системі числення і перевівши кожен з них в систему з основою n , отримаємо значення індексів:
| 1 2 3 4 5 6 7 8 9 10 11 | M: = round (IntPower (n, k)); for i: = 0 to M-1 do begin Number: = i; for p: = 0 to k-1 do begin Indexes [k - p]: = Number mod n; Number: = Number div n; end; DoSomething (Indexes); end; |
Ще раз відзначимо, що метод не універсальний і під кожну задачу доведеться придумувати щось своє.
Ще один чудовий приклад - обчислення за номером кроку перекладань в завданню про Ханойські вежах дивіться тут: http://algolist.manual.ru/maths/combinat/hanoi.php
Контрольні питання
1. Визначте, що зроблять наведені нижче рекурсивні процедури та функції.
(А) Що надрукує наведена нижче процедура при виклику Rec (4)?
| 1 2 3 4 5 6 7 | procedure Rec (a: integer); begin writeln (a); if a> 0 then Rec (a-1); writeln (a); end; |
(Б) Чому дорівнюватиме значення функції Nod (78, 26)?
| 1 2 3 4 5 6 7 8 9 10 | function Nod (a, b: integer): integer; begin if a> b then Nod: = Nod (a - b, b) else if b> a then Nod: = Nod (a, b - a) else Nod: = a; end; |
(В) Що буде надруковано наведеними нижче процедурами при виклику A (1)?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | procedure A (n: integer); procedure B (n: integer); procedure A (n: integer); begin writeln (n); B (n-1); end; procedure B (n: integer); begin writeln (n); if n <5 then A (n + 2); end; |
(Г) Що надрукує нижеприведенная процедура при виклику BT (0, 1, 3)?
| 1 2 3 4 5 6 7 8 9 10 | procedure BT (x: real; D, MaxD: integer); begin if D = MaxD then writeln (x) else begin BT (x - 1, D + 1, MaxD); BT (x + 1, D + 1, MaxD); end; end; |
2. Уроборос - змій, який пожирає власний хвіст (рис. 14) в розгорнутому вигляді має довжину L , діаметр біля голови D , товщину черевної стінки d . Визначте, скільки хвоста він зможе в себе впихнути і в скільки шарів після цього буде покладений хвіст?
Рис. 14. Розгорнутий Уроборос.
3. Для дерева на рис. 10а вкажіть послідовності відвідування вузлів при прямому, зворотному і кінцевому порядку обходу.
4. Зобразіть графічно дерево, заданий за допомогою вкладених дужок: (A (B (C, D), E), F, G).
5. Зобразіть графічно синтаксичне дерево для наступного арифметичного виразу:
Запишіть це вираження в зворотної польської записи.
6. Для наведеного нижче графа (рис. 15) запишіть матрицю суміжності і матрицю інцидентності.
Рис. 15.
1 2 3 4