Последние новости
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.3 1) а * a = a^2 2) a^2 * a^2 = a^4 3) a^4 * a = a^5 4) a^5 * a^5 = a^10 5) a^10 * a^5 = a^15 (В доп. память) 6) a^15 * a^15 = а^30 7) а^30 * а^30 = а^60 8) а^60 * a^60 = а^120 9) а^120 * а^120 = а^240 10)а^240 * a^15 = а^255 (а^15 находилось в памяти). 11.1 1) а * a = a^2 2) a^2 * a^2 = a^4 ... 5) a^16 * a^16 = a^32