Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

Задача № 25. Вычислить x
n
 
по алгоритму быстрого возведения в степень 
Формулировка. Даны натуральные числа x и n. Вычислить x
n
, используя алгоритм быстрого 
возведения в степень: 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
30 
( )
( )
n div 2
2
n div 2
2
,
если четно
,
если нечетно
n
x
n
x
x
x
n


= 
 ⋅

Решение. Разберем этот пока неясный алгоритм, представленный в нашей задаче лишь един-
ственной формулой. Легко понять, что указанное равенство имеет место: например, 3
4
= 3
4 div 2
= 
(3
2
)
2
= 9
2
= 81. 
Другой пример: 4
5
= 4 * (4
2
)
5 div 2 
= 4 * (4
2
)
2
= 4 * 16
2
= 4 * 256 = 1024
. Причем если 
выражение со степенью нельзя в один шаг преобразовать таким образом, то необходимо продол-
жить преобразование выражения вплоть до получения конечного ответа. Однако как теперь реали-
зовать эту схему? 
Рассмотрим пример немного сложнее. Вычислим 4
7
= 4 * (4
2
)
3
= 4 * (16)
3
= 4 * 16 * (16
2
)
1
= 4 * 
16 * 256 = 16384. 
Стоит обратить внимание на то, что на каждом шаге при вычислении изменяется 
только единственное обрабатывающееся число, а остальные множители выносятся однократно и 
необходимы только для получения ответа в последнем действии. 
Чтобы исключить их из рассмотрения, при нечетном текущем числе n мы будем домножать 
на них некоторую промежуточную переменную r, поначалу равную 1 (кстати, нечетность числа в