Последние новости
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.
11.1 1)*a=a^2 2)*a=a^3 3)*(a^3)=a^6 4)*a=a^7 5)*(a^7)=a^14 6)*a=a^15 7)*(a^15)=a^30 8)*a=a^31 9)*(a^31)=a^62 10)*a=a^63 11)*(a^63)=a^126 12)*a=a^127 13)*(a^127)=a^254 14)*a=a^255 Итого 14 операций 11.3 1)*a=a^2 2)*a=a^3, заносим a^3 в ячейку памяти 3)*(a^3)=a^6 4)*(a^6)=a^12 5)*(a^12)=a^24 6)*(a^24)=a^48 7)*(a^3)=a^51, a^3 из памяти, заносим в память a^51 8)*(a^51)=a^102 9)*(a^102)=a^204 10)*(a^51)=a^255, a^51 из памяти Итого 10 операций и 1 доп. ячейка памяти