Информатика • 10 класс

Алгоритм быстрого возведения в степень (Python)

Алгоритм бинарного (быстрого) возведения в степень использует рекурсию:
$a^{n} = \{\begin{matrix} 1, п р и n = 0, \\ a^{\frac{n}{2}} \cdot a^{\frac{n}{2}}, п р и (n m o d 2) = 0, \\ a^{n - 1} \cdot a, п р и (n m o d 2) = 1 . \end{matrix}$
Пример. Составьте программу быстрого возведения в степень.
Программный код:
```
def pow_fast (a, n):
if n == 0:
	return 1
elif n % 2 == 0:
	return pow_fast (a * a, n // 2) 
else:
	return a * pow_fast (a, n - 1) 
print (pow_fast (5, 7)) 
pow_fast (a, n)
```
// функция возведения числа a в степень n с использованием рекурсии и метода быстрого возведения в степень.

Было полезно?

Рекомендуем

Вы учитель или ученик?

Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ

Учителю

Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников

Ученику

Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках