WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Рекурсивні означення та підпрограми - Реферат

Рекурсивні означення та підпрограми - Реферат

пов'язано два важливих поняття - глибина рекурсії та загальна кількість викликів, породженихвикликом рекурсивної підпрограми.
Розглянемо перше з них. У прикладі 9.6 наведено функцію обчислення n!. Очевидно, що її виклик із аргументом, наприклад, 4, закінчується лише після закінчення виклику з аргументом 3, а той, у свою чергу, після виклику з аргументом 2 тощо. Такі виклики називаються вкладеними. Отже, виклик із аргументом 4 породжує ще три вкладені виклики.
Взагалі, за виклику з аргументом n породжується ще n-1 виклик, і загальна кількість незакінчених викликів досягає n. Отже, максимальна кількість незакінчених рекурсивних викликів при виконанні виклику підпрограми називається глибиною рекурсії цього виклику.
За виконання виклику з глибиною рекурсії m одночасно "існують" m екземплярів локальної пам'яті. Кожний екземпляр має певний розмір, і якщо глибина буде надто великою, то автоматичної пам'яті, яку надано процесу виконання програми, може не вистачити.
Друге поняття можна назвати загальною кількістю вкладених викликів, породжених викликом рекурсивної підпрограми. Ця кількість значною мірою впливає на час виконання виклику. Проілюструємо це наступним прикладом.
Приклад 9. За властивостями трикутника Паскаля, біноміальний коефіцієнт C(m,n)=1 при m 1 або n=0 або n=m; у противному разі
C(m,n)=C(m-1,n-1)+C(m-1,n).
Згідно цього означення напишемо рекурсивну функцію обчислення за m, n, де 0 n m, біноміального коефіцієнта C(m,n):
function C(m, n : integer) : integer;
begin
if (m1, 0tow(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 множень, хоча можна за допомогою 3-х множень обчислити x5, після чого помножити його на себе двічі (разом 5 множень). Проте написати алгоритм, який задає обчислення довільного степеня з мінімальною кількістю множень, - не зовсім проста задача. Залишимо її для наполегливих читачів.
Побудуємо нерекурсивний аналог наведеного алгоритму. Подамо обчислення за рекурсивним алгоритмом у такому вигляді:
x13 = (x6)2 x1 = ((x3)2 x0)2 x1 = (((x1)2 x1)2 x0)2 x1
Цьому відповідає така обробка показників степенів, що обчислюються:
13 = 6 2+1 = (3 2+0) 2+1 = ((1 2+1) 2+0) 2+1.
Як бачимо, обчисленню степенів відповідає обчислення значення 13, поданого поліномом відносно 2. Коефіцієнтами його є цифри двійкового розкладу числа 13. Неважко переконатися, що обчисленню степеня з довільним показником n так само відповідає обчислення n, представленого двійковим розкладом. Причому цей розклад-поліном записано за схемою Горнера. Розкриємо дужки в ньому:
1 23+1 22+0 21+1 20.
Коефіцієнти при 20, 21, 22 тощо - це послідовні остачі від ділення на 2 чисел
n, n div 2, (n div 2) div 2 тощо,
причому остачі 1 відповідає в рекурсивному алгоритмі присвоювання t:=x, а 0 - присвоювання t:=1. Таким чином, двійковий розклад, наприклад, числа 13 по степенях двійки відповідає такому поданню x13: x23 x22 1 x20.
Отже, достатньо обчислювати степені
x20=x, x21=x2, x22=(x2)2, x23=(x22)2 тощо
та відповідні їм остачі від ділення на 2 показників
n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 тощо,
накопичуючи в добутку лише ті двійкові степені, які відповідають остачам 1. У наступному алгоритмі добуток степенів накопичується в змінній t, а двійкові степені - в змінній x:
function pow(x, n : integer) : integer;
var t : integer; notfin : boolean;
begin
t:=1; notfin:=true;
while notfin do
begin
if odd(n) then t:=t*x;
n:=n div 2;
if n>0 then x:=x*x else notfin:=false
end;
pow:=t
end;
Loading...

 
 

Цікаве