Последние новости
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 = a^2 2) a^2 * a = a^3 3) a^3 * a^3 = a^6 4) a^6 * a = a^7 5) a^7 * a^7 = a^14 6) a^14 * a = a^15 7) a^15 * a^15 = a^30 8) a^30 * a = a^31 9) a^31 * a^31 = a^62 10) a^62 * a = a^63 11) a^63 * a^63 = a^126 12) a^126 * a = a^127 13) a^127 * a^127 = a^254 14) a^254 * a = a^255 11.2 и 11.3: Пусть ячейка памяти будет x 1) a * a = a^2 2) a^2 * a^2 = a^4 3) a^4 * a^4 = a^8 4) a^8 * a^8 = a^16 5) a^16 * a = a^17 x = a^17 6) a^17 * a^17 = a^34 7) a^34 * a^34 = a^68 8) a^68 * x = a^68 * a^17= a^85 x = a^85 9) a^85 * a^85 = a^170 10) a^170 * x = a^170 * a^85 = a^255