Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Опишите алгоритм возведения числа a в 255 степень с помощью только операции умножения:
11.1 За 14 операций умножения без использования дополнительной памяти (то есть разрешается использовать только исходное число и результат последней операции).
11.2 За 10 операций умножения с использованием любого количества дополнительной памяти.
11.3 За 10 операций умножения с использованием одной ячейки дополнительной памяти (то есть помимо исходного числа и результата последней операции, разрешается держать в памяти ещё одно число. Это число может меняться в процессе работы алгоритма).
Замечание: верное решение для 11.3 будет засчитываться и для 11.2.
a*a*a=a^3 (2 операции) a^3*a^3*a=a^7 (4 операции) a^7*a^7*a=a^15 (6 операции) a^15*a^15*a=a^31 (8 операции) a^31*a^31*a=a^63 (10 операции) a^63*a^63*a=a^127 (12 операции) a^127*a^127*a=a^255 (14 операции) Метод решение заключается в делением 255 на 2 без остатка с параллельным записыванием остатка.