За какое наименьшее число умножений можно найти:

  1. alt text;
  2. alt text?

задан 30 Янв '15 21:28

изменен 31 Янв '15 18:22

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

При самом простом подходе мы можем для нахождения $%x^{16}$% каждый раз домножать на $%x$%, начиная с $%x$%, делая это 15 раз. Однако можно обойтись меньшим числом умножений, если последовательно возводить числа в квадрат. Сначала находим $%x^2=x\cdot x$% (одно умножение). Далее умножаем $%x^2$% на себя (нам это значение известно), и получаем $%x^4$%. Это второе из умножений. При помощи третьего умножения по тому же принципу мы получим $%x^8=x^4\cdot x^4$%, и далее $%x^{16}=x^8\cdot x^8$%. Всего получится 4 умножения вместо 15.

Для нахождения $%x^{15}$%, с учётом того, что $%15=1+2+4+8$%, надо перемножить между собой четыре выражения: $%x^{15}=x\cdot x^2\cdot x^4\cdot x^8$%. К этому моменту нам известны значения всех этих сомножителей, на что ранее было затрачено три умножения. К ним добавится ещё 3, итого будет 6.

ссылка

отвечен 31 Янв '15 5:13

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,148
×51
×18

задан
30 Янв '15 21:28

показан
293 раза

обновлен
31 Янв '15 5:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru