Последние новости
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.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.3 (аналогично для 11.2) a - исходное число, b - ячейка памяти. 1) a*a=a^2 2) a^2*a=a^3. b=a^3. 3) a^3*a^3=a^6 4) a^6*a^6=a^12 5) a^12*a^12=a^24 6) a^24*a^24=a^48 7) a^48*b=a^48*a^3=a^51. b=a^51 8) a^51*a^51=a^102 9) a^102*a^102=a^204 10) a^204*b=a^204*a^51=a^255