Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Опишите алгоритм возведения числа a в 255 степень с помощью только операции умножения:
11.1 За 14 операций умножения без использования дополнительной памяти (то есть разрешается использовать только исходное число и результат последней операции).
11.2 За 10 операций умножения с использованием любого количества дополнительной памяти.
11.3 За 10 операций умножения с использованием одной ячейки дополнительной памяти (то есть помимо исходного числа и результата последней операции, разрешается держать в памяти ещё одно число. Это число может меняться в процессе работы алгоритма).
Замечание: верное решение для 11.3 будет засчитываться и для 11.2.
11.1 Фактически, это алгоритм перевода числа 1 в 255 при помощи только операции +1 и *2. Начнем с результата алгоритма (далее будут записаны только числа, которые участвуют в алгоритме) 255 254 127 126 63 62 31 30 15 14 7 6 3 2 1. Если обозначить операцию сложения как 1, а умножения как 2, то получаем следующий алгоритм возведения числа а в 255 степень 11212121212121 11.3 1*2=2 2*2=4 4*2=8 8*2=16 16+1=17 (запомнили 17) 17*2=34 34+17=51 (запомнили 51) 51*2=102 102*2=204 204+51=255