Последние новости
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 доп. ячейка памяти -- b 1) a * a = a^2 2) a^2 * a = a^3; b:= a^3 3) b * b = a^3 * a^3 = a^6 4) a^6 * a^6 = a^12 5) a^12 * b = a^12 * a^3 = a^15; b := a^15 6) b * b = a^15 * a^15 = a^30 7) a^30 * a^30 = a^60 8) a^60 * a^60 = a^120 9) a^120 * a^120 = a^240 10) a^240 * b = a^240 * a^15 = a^255