5
|
Задача 228. Эффективный метод возведения в степеньпостоянный адрес задачи: http://www.diofant.ru/problem/601/показать код для вставки на свой сайт >> |
Задачу решили:
10
всего попыток:
36
поделиться задачей:
|
|
|
Задача опубликована:
30.11.09 08:00
Прислал:
mikev
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
арифметика
|
|
|
Первое, что приходит в голову, когда нужно возвести число в 15-ю степень, это просто выполнить четырнадцать умножений:
n 
n ... n = n15
Если использовать "бинарный" метод, того же результата можно достичь, выполнив всего шесть умножений:
n n = n2
n2 n2 = n4
n4 n4 = n8
n8 n4 = n12
n12 n2 = n14
n14 n = n15
Но оказывается, что количество умножений можно сократить до пяти:
n n = n2
n2 n = n3
n3 n3 = n6
n6 n6 = n12
n12 n3 = n15
Определим m(k) как минимальное количество умножений, необходимое для вычисления nk; например, m(15) = 5.
Найдите наименьшее значение k, для которого m(k)=12.
Пожалуйста, не пишите нам, что Вы не можете решить задачу.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Внимание! В обсуждении задачи запрещено публиковать ответы и давать подсказки.