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

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

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

ПАСКАЛЬ: рекурсивні означення та підпрограми - Реферат

її залежність від аргументів. Скажемо лише, що за n=mdiv2 або n=mdiv2+1 вона більше, ніж 2m/2. Наприклад, за m=60 це 230, або приблизно 109. Якщо навіть припустити, що за секунду можна виконати 106 викликів, то треба більше 1000 секунд, тобто приблизно 20 хвилин. Проте неважко написати рекурсивну функцію, виклик якої з аргументом m породжує не більше, ніж m/2 вкладених викликів (задача 9.7).
Отже, вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди слід писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Принаймні, для обчислення біноміальних коефіцієнтів узагалі краще скористатися циклом (розділ 5.2). Справа в тім, що виконання кожного виклику підпрограми потребує додаткових дій комп'ютера, описаних у розділі 8. Тому "циклічний" варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також не слід уживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам'яті та аварійного завершення програми.
У цьому розділі ми розглядаємо лише так звану пряму рекурсію, коли підпрограма містить виклики самої себе. У програмуванні зустрічається також і непряма рекурсія, коли підпрограма містить виклики інших підпрограм, а ті - виклики цієї підпрограми. Приклади непрямої рекурсії та реалізацію її в мові Паскаль ми розглянемо в розділі 21.
Задачі
4.* Виразити словами залежнiсть значення, що повертається функцією
function sumdi ( n : integer ) : integer;
begin
if 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
elsepow:=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;
Задача
11. Імітувати виконання виклику функції pow (обидва варіанти) з аргументами x=2, n=11. Указати загальну кількість виконуваних арифметичних операцій при n = 5, 10, 15, 16, 1000, 1023, 1024.
Loading...

 
 

Цікаве