Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Приклад. «Індійський алгоритм» піднесення числа х до натурального степеня п реалізує таке рекурсивне означення степеня числа:

«Індійський алгоритм» піднесення числа х до натурального степеня п реалізує таке рекурсивне означення степеня числа:

Алгоритм обчислення хⁿ

1.Якщо показник степеня дорівнює нулю, то значення хⁿ покласти рівним одиниці та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 2-5.

2.Якщо показник степеня дорівнює одиниці, то значення хⁿ покласти рівним х та вийти з рекурсії, інакше виконати дії, зазначені в пунктах 3-5.

3.Обчислити значення х^{n div 2} та піднести його до квадрата.

4.Якщо показник степеня непарний, то обчислене в пункті 3 значення помножити на число х, а отриманий результат вважати значенням хⁿ.

5.Інакше, коли показник степеня парний, то обчислене в пункті 3 значення вважати значенням хⁿ.

program ех8_9:; {індійський алгоритм піднесення до степеня}

var base,exponent:integer; {число, показник степеня}

procedure Init;

begin

writeln (‘ Indian algorithm’);

writeln (‘enter base, exponent’);

readln (base,exponent);

end;

{============піднесення до степеня ==================}

function pow(x, n:integer):longint;

var t: integer; {допоміжна змінна}

begin

if n = 0 then pow:=l

else

if n = l then pow:= x {рекурсивне повернення}

else

begin

t:= sqr(pow(x, n div 2)); {рекурсивне занурення}

if odd(n) then pow:=t*x {рекурсивне повернення}

else pow:= t; {рекурсивне повернення}

end;

end;

{===========основна програма ===============}

begin

Init;

writeln (base, ‘٨’, exponent, '=', pow(base, exponent));

end.

Глибина рекурсії функції pow не перевищує log₂ п.