ПАСКАЛЬ: РЕКУРСИВНІ ОЗНАЧЕННЯ ТА ПІДПРОГРАМИ

а) C ( m, n ) = C ( m-1, n-1 )  m / n;

б) C ( m, n ) = C ( m, n-1 )  ( m-n+1 ) / n;

в) C ( m, n ) = C ( m, n+1 )  ( n+1 ) / ( m-n ).

Підрахувати в кожному варіанті загальну кількість виконань викликiв функції при обчисленні коефіцієнта за m=6, n=2 та за m=8, n=5.

7.* Написати варіант функції обчислення C(m,n), при виконанні якого завжди відбувається не більше, ніж m/2 рекурсивних викликів.

8. Проімітувати звернення до функції Gcd (приклад 9.8) з аргументами

а)15 і 25; б) 13 і 21; в) 1024 і 729.

10.* Для довiльного n>0 указати числа an та bn такi, що при обчисленнi НСД(an,bn) за допомогою функції Gcd з прикладу 9.8 загальна кiлькiсть виконань викликiв дорiвнює n.

3. "Ханойські вежі"

На дошці є три голки: 1, 2, 3. На голці 1 розміщена вежа з n дисків; нижній диск має найбільший діаметр, а діаметр кожного наступного менший від попереднього. За один хід із будь-якої голки можна взяти верхній диск і перемістити на іншу, але дозволено класти диск лише на дошку або на диск більшого діаметра. Треба перемістити усю вежу з голки 1 на голку 3.

Ця гра називається "Ханойські вежі", оскільки за легендою з n=64 дисками її почали понад 1000 років тому ченці в одному монастирі поблизу Ханоя у В'єтнамі; коли вони закінчать її, настане кінець світу. Розв'язанням цієї гри-задачі є послідовність перенесень дисків. Написати програму друкування позначень цих перенесень.

Для перенесення вежі висотою n дисків з голки 1 на голку 3 необхідно перенести вежу висотою n-1 на голку 2, потім перенести нижній диск на голку 3 та перенести вежу з голки 2 на голку 3. При перенесенні вежі з 1 на 2 допоміжною є голка 3, а при перенесенні з 2 на 3 – голка 1. Інша послідовність дій неможлива. Отже, розв'язання задачі для вежі висотою n описується через розв'язання задачі для вежі висотою n-1.

Позначимо disk(a,b) перенесення одного диску з голки a на голку b, tow(h, a, b, c) – перенесення вежі висотою h з голки a на b з використанням голки c як допоміжної (tow – це скорочення від tower, або вежа). За h>1 виконання tow(h, a, b, c) зводиться до виконання

tow(h-1, a, c, b); disk(a, b); tow(h-1, c, b, a),

а за h=1 – до виконання

disk(a, b).

Отже, маємо програму:

program Hantow(input, output);

var n : integer;

procedure disk(f, t : integer);

begin writeln(f, '->', t) end;