ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2340
Скачиваний: 1
66
Декомпозиція являє собою зведення загального випадку до більш
простих підзадач, які відрізняються від вихідної задачі набором вхідних
даних. Декомпозиційні залежності описують не тільки зв'язок між задачам і
підзадачами, а й характер зміни значень параметрів на черговому кроці. Від
обраних відносин залежить трудомісткість алгоритму, так як для однієї і тієї
ж задачі можуть бути складені різні залежності. Перегляд відносин
декомпозиції доцільно проводити комплексно, тобто паралельно з
коригуванням параметрів і аналізом базових випадків.
Існує декілька категорій завдань, що допускають рекурсивні визначення.
Одна з категорій – математичні формули, визначення яких рекурсивне за
своєю суттю.
Основним завданням дослідження рекурсивних функцій є отримання
F(n)
в явній або як ще кажуть «замкнутій» формі, тобто у вигляді аналітично
заданої функції.
Класичний приклад функції, визначення якої може задаватися в
рекурсивної формі, F (n) = n!
F(n)=n*(n-1)*…*1, 0!=1
Рекурсивне визначення цієї функції має вид:
1,
0
( )
* (
1),
0
n
F n
n F n
n
=
=
− >
де F(n-1)=(n-1)!
Другий приклад – це опис синтаксису конструкцій мов програмування за
допомогою Бэкуса Наура форми (БНФ).
Приклад.
Визначення ідентифікатора в мові Паскаль: зараз С++
<літера>::=a|b|…|z,
<цифра>::=0|1|…|9;
<ідентифікатор>::=<літера>|<ідентифікатор><літера>|<ідентифікатор><цифра>.
8.2.
Рекурсивні процедури і функції
Категорії задач, що дозволяють рекурсивні визначення:
67
1.
Задачі, математичні моделі яких записуються у вигляді рекурсивно
визначених функцій.
2.
Структура даних задачі визначаться рекурсивним чином. Наприклад:
графи, дерева, списки.
3.
Методи рішення задачі допускають рекурсивне визначення (ігри,
головоломки тощо)
Рекурсивні алгоритми реалізуються у вигляді підпрограм, які
визначаються в програмі, як процедури або функції.
Підпрограма називається рекурсивною, якщо в її визначенні присутній
прямо або побічно виклик самої обумовленої підпрограми.
Явна рекурсія характеризується існуванням у визначеній підпрограмі
оператора звернення до неї самої.
Неявна (непряма) рекурсія характеризується тим, що одна підпрограма
звертається до іншої, яка через ланцюжок викликів інших підпрограм
рекурсивно звертається до першої.
Реалізація рекурсивних підпрограм
Стек – структура даних, яка містить впорядкований набір елементів.
Якщо в стек заноситься новий елемент, він додається в кінець
упорядкованого набору (на вершину стека). При видаленні елемента він теж
вибирається з кінця набору (з вершини стека).
В основі реалізації рекурсивної підпрограми лежить структура даних, що
називається стеком, в якому зберігаються всі не глобальні дані, що беруть
участь у всіх викликах підпрограми, при яких вона ще не завершила свою
роботу.
Стек складається з фрагментів, які становлять блоки послідовних
осередків.
Кожен виклик підпрограми використовує фрагмент стека, довжина якого
залежить від підпрограми, що викликається.
У загальному випадку при виклику процедурою А процедури В
відбувається наступне:
1.
В вершину стека поміщається фрагмент потрібного розміру. До нього
входять такі, дані:
(
а) показники фактичних параметрів виклику процедури В;
(б) порожні комірки для локальних змінних, визначених у процедурі В;
(
в) адреса повернення (АВ), тобто адреса команди в процедурі А, яку слід
виконати після того, як процедура В закінчить свою роботу.
68
Якщо В – функція, то у фрагмент стеку для В поміщається покажчик
осередку у фрагменті стека для А, в якій належить помістити значення цієї
функції (адреса значення).
2. Управління передається першому оператору процедури В.
3.
При завершенні роботи процедури В управління передається
процедурі А за допомогою наступної послідовності кроків:
(
а) адреса повернення витягується з вершини стеку;
(б) якщо В – функція, то її значення запам'ятовується в комірці, на яку
вказує покажчик адреси значення;
(
в) фрагмент стека процедури В витягується з стека, в вершину ставиться
фрагмент процедури А;
(г) виконання процедури А поновлюється з команди, зазначеної в адресі
повернення.
При виклику підпрограмою самої себе, тобто в рекурсивному випадку,
виконується та ж сама послідовність дій.
Рекурсивне визначення складається з двох незалежних частин: базової і
рекурсивної.
Базова частина не є рекурсивним ствердженням, вона задає визначення
для деякої фіксованої групи об'єктів і визначає умову закінчення рекурсії. У
першому прикладі в базовій частині стверджується, що об'єкт 0! = 1.
Рекурсія і ітерація
Не завжди рекурсивне рішення задачі є кращим, більш прості рішення
можуть бути знайдені за допомогою ітерації. Клас функцій, що мають
визначення виду
1
( ),
0,
( )
(
( )),
0.
n
n
G x
если n
F x
H F
x
если n
−
=
=
>
може завжди бути виражений ітеративно так, що застосування рекурсії
необов'язково.
Приклад. Необхідно скласти визначення функції для обчислення значений
деяких поліномів, визначення яких має наступний вигляд:
69
1
2
0,
0,
( )
2 ,
1,
2
1
( )
( ),
n>1
1
2
n
n
n
если n
S x
x
если n
n
n
S
x
S
x
если
n
n
−
−
=
=
=
−
+
−
Розглянемо ряд прикладів:
б) Приклади рекурсивних функцій
1.
ƒ(0)=0
ƒ(n)= ƒ(n-1)+1
Зрозуміло, що ƒ(n)=n.
2.
ƒ(0)=1
ƒ(n)= n*ƒ(n-1)
Послідовна підстановка дає – f(n) = 1*2*3* ... *n = n!
Для повноти відомостей наведемо формулу Стірлінга для наближеного
обчислення факторіала для великих n:
n!
≈
(2
π
n)
1/2
*(n
n
)/(e
n
)
3.
ƒ(0)=1
ƒ(1)=1
ƒ(n)= ƒ(n-1)+ ƒ(n-2), n
≥
2
Ця рекурсивна функція визначає числа Фібоначчі: 1 1 2 3 5 8 13, які
досить часто виникають при аналізі різних завдань, у тому числі і при аналізі
алгоритмів. Відзначимо, що асимптотично f (n) » [1,618 n] [8].
4.
ƒ(0)=1
ƒ(n)= ƒ(n-1)+ ƒ(n-2)+…+1 =
∑
ƒ(i)+1
Для отримання функції в явному вигляді розглянемо її послідовні
значення: ƒ(0)=1, ƒ(1)=2, ƒ(2)=4, ƒ(3)=8, що дозволяє припустити, що
ƒ(n)=2
n
,
точний доказ виконується по індукції.
70
5.
ƒ(0)=1
ƒ(n)= 2*ƒ(n-1)
Ми маємо справу з прикладом того, що одна і та ж функція може мати
різні рекурсивні визначення – f(n) = 2n, як і в прикладі 4, що перевіряється
елементарною підстановкою.
6.
ƒ(0)=1
ƒ(1)=2
ƒ(n)= ƒ(n-1)*ƒ(n-2)
У цьому випадку ми можемо отримати рішення в замкнутій формі,
зіставивши значенням функції відповідають ступені двійки:
ƒ(2) = 2 = 2
1
ƒ(3) = 4 = 2
2
ƒ(4) = 8 = 2
3
ƒ(5) = 32 = 2
5
ƒ(6) = 256 = 2
8
Позначаючи через F
n
– n -
ое число Фібоначчі, маємо: ƒ(n)=2
Fn
.
8.3
Аналіз трудомісткості рекурсивних алгоритмів методом
підрахунку вершин дерева рекурсії
Рекурсивні алгоритми відносяться до класу алгоритмів з високою
ресурсоємністю, так як при великій кількості самовивозу рекурсивних
функцій відбувається швидке заповнення стекової області. Крім того,
організація зберігання та закриття чергового шару рекурсивного стека є
додатковими операціями, які вимагають тимчасових витрат. На
трудомісткість рекурсивних алгоритмів впливає і кількість переданих
функцією параметрів.
Розглянемо один з методів аналізу трудомісткості рекурсивного
алгоритму, який будується на основі підрахунку вершин рекурсивного дерева.
Для оцінки трудомісткості рекурсивних алгоритмів будується повне дерево