а) 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;

procedure tow(h : integer; f, t, v : integer);

begin

if h=1 then disk(f, t) else

begin

tow(h-1, f, v, t); disk(f, t); tow(h-1, v, t, f)

end

end;

begin readln(n); tow(n, 1, 3, 2) end.

Очевидно, що глибина рекурсії викликів цієї процедури дорівнює значенню їх першого аргументу h.

Визначимо кількість переносів дисків як функцію f(n), де n – висота вежі. Очевидно, що f(1)=1, і що f(n)=2? f(n-1)+1. За принципом індукції неважко довести, що f(n)=2n-1. Значення f(64) дорівнює приблизно 1022. Якщо припустити, що кожної секунди ченці переносять один диск, то для переносу такої вежі потрібно приблизно 1015 років! Навіть якщо припустити, що комп'ютер здатний щосекунди друкувати по сто тисяч позначень переносів, то й тут знадобиться 1010 років. Кінець світу, мабуть, настане раніше…

4. "Індійський алгоритм" піднесення до степеня

Цей алгоритм обчислення натурального n-го (n>0) степеня цілого числа x виглядає зовсім просто:

за n=1 xn = x,

за n>1 xn = xn mod 2? (xn div 2)2.

Основна мета цього алгоритму – скоротити кількість множень при піднесенні до степеня. Наприклад, за цим алгоритмом x5=x? (x2)2, тобто достатньо три множення замість чотирьох: x? x? x? x? x. Одне множення економиться за рахунок того, що x2 зберігається як проміжне значення і множитися само на себе. Так само x10=1? (x5)2=(x5)2, що вимагає лише чотирьох множень (три з них для обчислення x5) замість дев'яти "лобових". Але тут доведеться зберігати спочатку x2, а потім x5.

Як бачимо, обчислення xn зводиться до обчислення xndiv2, запам'ятання його, піднесення до квадрату, та множення його на x за непарного n. Отже, обчислення xn описується рекурсивною функцією

function pow(x, n : integer) : integer;

var t : integer;

begin

if odd(n) then t:=x

else t:=1;

if n=1 then pow:=x

else pow:=t*sqr(pow(x, n div 2))

end;

Як бачимо, проміжні множники зберігаються в локальній пам'яті процесів виконання викликів функції, а саме в тих змінних, що ставляться у відповідність її імені.

Тепер спробуємо описати залежність глибини рекурсії викликів функції від значення аргументу. У кожному наступному вкладеному виклику значення аргументу n менше від попереднього значення принаймні вдвічі. Оскільки за n=1 відбувається повернення з виклику, то таких зменшень значення аргументу n не може бути більше, ніж log2n. Отже, глибина рекурсії виклику з аргументом n не перевищує log2n.

Таку глибину можна вважати доброю властивістю алгоритму. При кожному виконанні виклику відбувається не більше одного ділення, піднесення до квадрату та множення, тому загальна кількість арифметичних операцій не більше 3log2n. За великих значень n це суттєво менше "лобових" n-1 множень. Наприклад, за n=1000 це приблизно 30.

Зауважимо, що при деяких значеннях n наведений алгоритм не дає найменшої кількості множень, необхідних для обчислення n-го степеня. Наприклад, при n=15 за цим алгоритмом необхідні 6 множень,