4. Вивчення нового матеріалу.

Розглянемо приклади розв'язування задач з використанням рекурсії.

Приклад 16.

Ханойські вежі (рекурсивний алгоритм роз­в'язування головоломки)

Є три стрижні, на одному з яких зібране N дисків. Потрі­бно перекласти їх на третій стрижень, користаючись дру­гим як допоміжним, за прави­лами: диски можна перекла­дати тільки по одному і' не можна класти більший диск на менший.

Розглянемо добре відому задачу про Ханойські вежі.

У легенді розповідається, як монахи одного Ханойського монастиря перекладали 64 великі диски, що утримували на подвір’ї три вежі А,В,С. За легендою, кінець світу мав настати в момент, коли осатаній диск ляже на вершину вежі С з дотриманням певних правил.

Отже, є 3 вісі (А,В,С) і n дисків. Диски можна нанизувати на вісі, утворюючи таким чином вежі.

Нехай спочатку диски знаходяться на вісі А у порядку зменшення розміру (для n=4 ситуацію пояснює мал.1).

Рис.1. Задача «Ханойські вежі» для випадку 4-х дисків

Розв'язок.

Позначимо X - початковий стрижень, У - проміж­ний, Z - кінцевий стрижень, N - кількість дисків на стрижні.

Опис алгоритму розв'язування задачі має вигляд інструкції щодо перекладання дисків:

• Якщо N= 0, зупинитись.

• Крок 1: перекласти (N-1) дисків з X на стрижень Y, використо­вуючи стрижень Z як допоміжний.

• Крок 2: перекласти диск N з X на стрижень Z.

• Крок 3: перекласти (iV-І) дисків з Y на стрижень Z, використо­вуючи стрижень X як допоміжний.

Program Hanoy;

Const N=3;

Var X, y, z : char;

Procedure Per (K:lnteger; X,Y,Z:Char);

Begin

if K>0 Then Begin

per (K-1, X, Z, Y);

writeLn ('Диск ‘,к, ‘ з ',x, ‘ на ‘, z);

per (к-1, Y, x, z);

    End;

K:=K+1;

End;

Begin

Per (N, 'X', 'Y', 'Z');

End.

Результат роботи програми для N=3 складається з семи кроків (для N=4 - з 15 кроків):

Приклад 17.

Одержати всі послідовності з чисел -1, 0, 1 довжини N.

Розв'язок.

Основна ідея рекурсивного алгоритму: покладемо пе­рший елемент послідовності а1= -1 і "приставимо" до нього ВСІ послідовності на одиницю меншої довжини. Одержимо частину розв'язку вихідної задачі. Повторивши ті ж дії для а1=0 і а1=1, одер­жимо повний розв'язок задачі. Задавши перед звертанням до процедури Per, яка реалізує рекурсивний алгоритм, К=1, одержимо послідовність а1=- 1, а2=-1, а3= -1, ... аn= -1. Очевидно, що при K=N+1 алгоритм повинний вивести отриману послідовність (для цього змінні a1... aN варто розглядати як елементи таблиці a[1..N]) і повернутися для продовження роботи на N-й рівень рекурсії.

Const N=3;

Var і, к, j : integer;

A: Array [1..N] of Integer;

Procedure Per (Var K:lnteger);

Begin

if K=N+1 Then Begin

For i:=l To N Do write (A[i]:3);

WriteLn; J:=J+1

End

Else Begin A[K]:=-1;

while A[K]<=1 Do Begin K:=K+1;

Per(K);

A[K]:=A[K]+1;

   End;

End;

к:=к-1; {повернення на 1 елемент влівоj

End;

Begin ,

J:=0; K:=l;

Per (K);

WriteLn ('J=', J);

End.

Приклад 18.

«Сходинки». Людина піднімається східцями, ступаючи на насту­пну сходинку, або перестрибуючи через одну чи дві сходинки. Знайти, скількома способами вона зможе піднятися на N-y сходинку (N<30).

Розв'язок.

Кількість способів можна визначити, обчислюючи варіанти у зворотньому порядку — від пе­редостанньої сходинки до першої. Позначимо через S(і) кількість способів, якими можна дістатися з i-ї сходинки на /V—у. Тоді S(N-1) = 1, S(N-2) = 2, S(N-3) = 4 — визначаємо безпосередньо, «вручну».

S (N-4)= S (N-1) + S (N-2) + S (N-3) = 13.

А далі повторюється циклічно за формулою:

S(i) = S(і+1) + S(і+2) + S(і+3), при і = N-4, N-5, N-6,..., 1, 0.

Відповідь дорівнює S(0).

Цю задачу можна розв'язати також рекурсивним алгоритмом, взявши за основу наведену формулу: