Задача
Бинарный метод возведения в степень.Предположим, что необходимо возвести числоxв степеньn. Если, например,n= 16, то это можно сделать выполнив 15 умноженийx16=x . x . ... . x, а можно обойтись лишь четырьмя:
x1 = x . x = x2, x2 = x1 . x1 = x4, x3 = x2 . x2 = x8, x4 = x3 . x3 = x16.
Пусть
n = 2e1 + 2e2 +...+ 2er (e1 > e2 >...> er $\displaystyle \geqslant$ 0).
Придумайте алгоритм, который позволял
бы вычислятьxnпри помощи
b(n) = e1 + $\displaystyle \nu$(n) - 1
умножений, где$\nu$(n) =r — число единиц в двоичном представлении числаn.
Решение
Решение задачи отсутствует
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет