Последние новости
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 a*a*a=a^3 (2d), b=a^3, (a^3)^2 (3d), (a^3)^4 (4d), (*b) (a^3)^5 (5d), b=(a^3)^5, ((a^3)^5)^2 (6d), ((a^3)^5)^4 (7d), ((a^3)^5)^8 (8d), ((a^3)^5)^16 (9d), (*b) ((a^3)^5)^17 (10d). все результаты получены путем умножения последнего получившегося числа на само себя (если указано (*b), значит последнее число умножили на b и получили следующее) 11.1 a^2 (1d) * a= a^3 (2d) * a^3 =a^6 (3d) *a= a^7 (4d) * a^7= a^14 (5d) *a= a^15 (6d) *a^15=a^30 (7d) * a= a^31 (8d) * a^31= a^62 (9d) * a= a^63 (10d) * a^63=a^126 (11d) *a=a^127 (12d) * a^127= a^254 (13d) *a= a^255 (14d)