Сторінка
4

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

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.