Задача 60903

Темы:    [ Теория алгоритмов (прочее) ] [ Примеры и контрпримеры. Конструкции ]

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

Условие

Пусть l (n) — наименьшее число умножений, необходимое для нахождения xⁿ. На примере чисел n = 15 и n = 63 покажите, что бинарный метод возведения в степень (смотри задачу 5.64) не всегда оптимален, то есть для некоторых n выполняется неравенство l (n) < b(n).

Решение

b(15) = 6, но l (15) = 5:

x₁ = x², x₂ = x₁ ^. x = x³, x₃ = x₁ ^. x₂ = x⁵, x₄ = x₃² = x¹⁰, x₅ = x₃ ^. x₄ = x¹⁵.

Аналогично l (63) = 8 < 10 = b(63).

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

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