В питере задали на экзамене: вычислить [math] при помощи не более чем 7 умножений.
С 8 ясно, вычислить 2,4....32 степень и согласно двоичному разложению 43 некоторые перемножить.
UPD. oeis тоже говорит, что за 7 возможно
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7[math]
но не говорит как) http://oeis.org/A003313
Оптимальность алгоритма бинарного возведения в степень
Оптимальность алгоритма бинарного возведения в степень
Ian писал(а):Source of the post но не говорит как) http://oeis.org/A003313
Там по ссылке есть дерево глубины 5 (в "example"). Из него видно, что 43=20+20+3. Эти два сложения плюс пять сложений для получения 20 (3 получается в процессе) дают семь сложений.
20=10+10
10=5+5
5=3+2
3=2+1
2=1+1
Последний раз редактировалось zykov 19 июн 2018, 18:49, всего редактировалось 1 раз.
Оптимальность алгоритма бинарного возведения в степень
Думаю, школьник для решения должен начать строить это дерево от 1. Достаточно 3 уровней. После достижения 5 уже очевидно - 5*8+3.
Оптимальность алгоритма бинарного возведения в степень
Интересно, почему Вы решили что это был школьник . Другие вопросы были на группы Галуа, цепные дроби, и на все час с мелочьюzykov писал(а):Думаю, школьник для решения должен начать строить это дерево от 1. Достаточно 3 уровней. После достижения 5 уже очевидно - 5*8+3.
Оптимальность алгоритма бинарного возведения в степень
Ian писал(а):Source of the post Интересно, почему Вы решили что это был школьник
Невнимательно прочитал. Написано "экзамен", а я подумал "олимпиада".
Оптимальность алгоритма бинарного возведения в степень
Только я не согласен, что дерево Кнута не продолжается на 7й уровень до 43, почему там именно 43 упоминают как исключение.Действительно, его заполнение неоднозначно, 40 можно получить на 6м уровне и как 32+8 но это не приведет к решению. То есть нельзя составить дерево, на котором цепи к каждому числу одновременно оптимальны, но с 43 как раз то, что приведено, хорошо дополняется
Код: Выбрать все
1
|
2
/ \
/ \
/ \
/ \
/ \
3 4
/ \ \
/ \ \
/ \ \
/ \ \
5 6 8
/ \ | / \
/ \ | / \
7 10 12 9 16
/ / \ / \ / \ / \
14 11 20 15 24 13 17 18 32
...........\.....
............40.......
..............\.....
...............43....
Оптимальность алгоритма бинарного возведения в степень
Там про 43 ничего такого не написано.
Там написано про тройку (43, 77, 149), что нет дерева, где все три были бы одновременно оптимальны.
Там написано про тройку (43, 77, 149), что нет дерева, где все три были бы одновременно оптимальны.
Вернуться в «Computer Science»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей