Задача
Пустьl(n) — наименьшее число умножений, необходимое для нахожденияxn. На примере чиселn= 15 иn= 63 покажите, что бинарный метод возведения в степень (смотри задачу5.64) не всегда оптимален, то есть для некоторыхnвыполняется неравенствоl(n) <b(n).
Решение
b(15) = 6, ноl(15) = 5:
x1 = x2, x2 = x1 . x = x3, x3 = x1 . x2 = x5, x4 = x32 = x10, x5 = x3 . x4 = x15.
Аналогичноl(63) = 8 < 10 =b(63).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет