ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Все авторы >> Белага Э.Г.

Фильтр
Сложность с по   Класс с по  
Все задачи автора

Страница: 1 [Всего задач: 1]      



Задача 73775

Темы:   [ Теория алгоритмов (прочее) ]
[ Двоичная система счисления ]
[ Показательные неравенства ]
[ Логарифмические неравенства ]
Сложность: 6+
Классы: 9,10,11

По заданному ненулевому x значение x8 можно найти за три арифметических действия: x2 = x · x, x4 = x2 · x2, x8 = x4 · x4, а x15 за пять действий: первые три — те же самые, затем x8 · x8 = x16 и x16 : x = x16. Докажите, что

а) x16 можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log2n действий.
Прислать комментарий     Решение


Страница: 1 [Всего задач: 1]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .