Паскаль: рекурсивні означення та підпрограми, Детальна інформація

в) C ( m, n ) = C ( m, n+1 ) \xF0A0 ( 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\xF0D7 f(n-1)+1. За принципом індукції неважко довести, що f(n)=2n-1. Значення f(64) дорівнює приблизно 1022. Якщо припустити, що кожної секунди ченці переносять один диск, то для переносу такої вежі потрібно приблизно 1015 років! Навіть якщо припустити, що комп'ютер здатний щосекунди друкувати по сто тисяч позначень переносів, то й тут знадобиться 1010 років. Кінець світу, мабуть, настане раніше…

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