Паскаль: рекурсивні означення та підпрограми, Детальна інформація
Паскаль: рекурсивні означення та підпрограми
Цей алгоритм обчислення натурального n-го (n>0) степеня цілого числа x виглядає зовсім просто:
за n=1 xn = x,
за n>1 xn = xn mod 2\xF0D7 (xn div 2)2.
Основна мета цього алгоритму – скоротити кількість множень при піднесенні до степеня. Наприклад, за цим алгоритмом x5=x\xF0D7 (x2)2, тобто достатньо три множення замість чотирьох: x\xF0D7 x\xF0D7 x\xF0D7 x\xF0D7 x. Одне множення економиться за рахунок того, що x2 зберігається як проміжне значення і множитися само на себе. Так само x10=1\xF0D7 (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\xF0B4 x1 = ((x3)2\xF0B4 x0)2\xF0B4 x1 = (((x1)2\xF0B4 x1)2\xF0B4 x0)2\xF0B4 x1
Цьому відповідає така обробка показників степенів, що обчислюються:
13 = 6\xF0B4 2+1 = (3\xF0B4 2+0)\xF0B4 2+1 = ((1\xF0B4 2+1)\xF0B4 2+0)\xF0B4 2+1.
Як бачимо, обчисленню степенів відповідає обчислення значення 13, поданого поліномом відносно 2. Коефіцієнтами його є цифри двійкового розкладу числа 13. Неважко переконатися, що обчисленню степеня з довільним показником n так само відповідає обчислення n, представленого двійковим розкладом. Причому цей розклад-поліном записано за схемою Горнера. Розкриємо дужки в ньому:
1\xF0B4 23+1\xF0B4 22+0\xF0B4 21+1\xF0B4 20.
Коефіцієнти при 20, 21, 22 тощо – це послідовні остачі від ділення на 2 чисел
n, n div 2, (n div 2) div 2 тощо,
причому остачі 1 відповідає в рекурсивному алгоритмі присвоювання t:=x, а 0 – присвоювання t:=1. Таким чином, двійковий розклад, наприклад, числа 13 по степенях двійки відповідає такому поданню x13: x23\xF0B4 x22\xF0B4 1\xF0B4 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 тощо,
за n=1 xn = x,
за n>1 xn = xn mod 2\xF0D7 (xn div 2)2.
Основна мета цього алгоритму – скоротити кількість множень при піднесенні до степеня. Наприклад, за цим алгоритмом x5=x\xF0D7 (x2)2, тобто достатньо три множення замість чотирьох: x\xF0D7 x\xF0D7 x\xF0D7 x\xF0D7 x. Одне множення економиться за рахунок того, що x2 зберігається як проміжне значення і множитися само на себе. Так само x10=1\xF0D7 (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\xF0B4 x1 = ((x3)2\xF0B4 x0)2\xF0B4 x1 = (((x1)2\xF0B4 x1)2\xF0B4 x0)2\xF0B4 x1
Цьому відповідає така обробка показників степенів, що обчислюються:
13 = 6\xF0B4 2+1 = (3\xF0B4 2+0)\xF0B4 2+1 = ((1\xF0B4 2+1)\xF0B4 2+0)\xF0B4 2+1.
Як бачимо, обчисленню степенів відповідає обчислення значення 13, поданого поліномом відносно 2. Коефіцієнтами його є цифри двійкового розкладу числа 13. Неважко переконатися, що обчисленню степеня з довільним показником n так само відповідає обчислення n, представленого двійковим розкладом. Причому цей розклад-поліном записано за схемою Горнера. Розкриємо дужки в ньому:
1\xF0B4 23+1\xF0B4 22+0\xF0B4 21+1\xF0B4 20.
Коефіцієнти при 20, 21, 22 тощо – це послідовні остачі від ділення на 2 чисел
n, n div 2, (n div 2) div 2 тощо,
причому остачі 1 відповідає в рекурсивному алгоритмі присвоювання t:=x, а 0 – присвоювання t:=1. Таким чином, двійковий розклад, наприклад, числа 13 по степенях двійки відповідає такому поданню x13: x23\xF0B4 x22\xF0B4 1\xF0B4 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 тощо,
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021