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

Проект МЦНМО
при участии
школы 57
Задача 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 действий.

Решение

Заметим сначала, что степени x с показателями 2 , 4 , 8 , ... , 2k можно вычислить за k умножений, именно: x2=x · x , x4=x2 · x2 , ... , x2k=x2k-1 · x2k-1 . Отсюда следует, что xn= x2log _2 n нельзя найти быстрее чем за l=[log _2 n] операций (через [z] обозначена целая часть действительного числа z , т.е. такое целое число m , что m z<m+1 ).

а) Так как 29=512<1000<1024=210 , т.е. [log _2 1000]=9 , то x1000 нельзя вычислить быстрее чем за 9 действий. С другой стороны, x1000= x1024:(x16 · x8) , на что потребуется 11 умножений и 1 деление. Можно доказать, что этот способ вычисления самый экономный.

Замечание. В "Кванте" #11 за 1973 год была опубликована задача из книжки Е.А.Морозовой и И.С.Петракова, Международные математические олимпиады:

Дан ящик сахарного песка, чашечные весы и гирька в 1 г. Как возможно быстрее отвесить покупателю 1 кг сахару? (Указать схему уравновешиваний.)

Несмотря на различие в формулировках, в действительности задачи M240а) и только что приведенная в точности совпадают, и теперь вы уже можете указать ответ и на этот вопрос.

б) Опишем теперь способ вычисления xn . Он основывается на двоичном представлении n 2 числа n .

Представим n в виде суммы

n=εl · 2ll-1 · 2l-1+...+ ε1 · 20,

где εj – либо 0 , либо 1 , 0 j l-1 , а εl=1 . Тогда двоичное представление n имеет вид:
n 2l εl-1 ... ε1 ε0 (*)


Обозначим через E(n) число единиц среди цифр εj :

1 εll-1+...+ε10= E(n) l+1,

а через H(n) – число нулей, так что H(n)=l+1-E(n) . Для нахождения xn вычисляем сначала многочлены x2 , x4 , ... , x2l (за l умножений). Дальнейшие вычисления зависят от величины E(n) .

(1) Если 1 E(n) , то перемножим те многочлены x2j , для которых εj=1 (для этого нам потребуется E(n)-1 умножений); ввиду равенства (*) , результат ранен xn , общее же число умножении равно l+E(n)-1 .

Но

l+E(n)-1 l+< log _2 n+1.


(2) Если <E(n) l+1 , то

H(n) .

Рассмотрим число =2l+1-n . Очевидно, что n 2+ 2=10 ... 0 ( l+1 нуль) и что поэтому E () H(n)+1 . Как и в случае (1), вычислим многочлен x за l+E()-1 умножений. Затем вычислим многочлен x2l+1 (так как многочлен x2l уже найден, то на это потребуется еще одно умножение) и, наконец, многочлен xn=x2l+1: x (одно деление). Итак, в этом случае потребовалось l+ E () умножений и одно деление, т.е. всего l+E () +1 действий, где
l+E ()+1 l+H(n)+2 l+1 log _2 n+1.


Замечание. Многочлен x1000 был вычислен нами способом(2). Однако существуют многочлены, для которых ни способ(1), ни способ(2) не являются наилучшими. Например, многочлен x170 может быть вычислен за 9 умножений (найдите такой способ сами!), хотя 170 2=10,101,010 , так что E(170)=H(170)=4 , [log _2 170]=7 ; при способе(1) нужно 10 умножений, а при способе(2)– 11 умножений и одно деление.

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

журнал
Название "Квант"
год
Год 1973
выпуск
Номер 12
Задача
Номер М240

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

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