Задача 60902

Темы:    [ Теория алгоритмов (прочее) ] [ Двоичная система счисления ]

Сложность: 3+ Классы: 8,9,10

Условие

Бинарный метод возведения в степень. Предположим, что необходимо возвести число x в степень n. Если, например, n = 16, то это можно сделать выполнив 15 умножений x¹⁶ = x ^. x ^. ... ^. x, а можно обойтись лишь четырьмя:

x₁ = x ^. x = x²,    x₂ = x₁ ^. x₁ = x⁴,    x₃ = x₂ ^. x₂ = x⁸,    x₄ = x₃ ^. x₃ = x¹⁶.

Пусть

n = 2^e₁ + 2^e₂ +...+ 2^e_r        (e₁ > e₂ >...> e_r 0).

Придумайте алгоритм, который позволял бы вычислять xⁿ при помощи

b(n) = e₁ + (n) - 1

умножений, где (n) = r — число единиц в двоичном представлении числа n.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	3
Название	Двоичная и троичная системы счисления
Тема	Двоичная система счисления
задача
Номер	05.064