Последние новости
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 255 это (2^8)-1, а при умножении степени складываются, следовательно при умножении числа на самого себя можно получить либо 128, либо 256 степень, что не подходит, воспользуемся методом перевода числа из 10-ой системы в 2-ную только в обратном порядке, т.е. сначала умножим результат на самого себя, а следующим действием результат последней операции *а: 1) а*а=a^2; 2)(a^2)*a=a^3; 3)(a^3)*(a^3)=a^6; 4) (а^6)*а=a^7; 5)(a^7)*(a^7)=a^14; 6) (a^14)*а=a^15; 7)(a^15)*(a^15)=a^30; 8) (a^30)*а=a^31; 9)(a^31)*(a^31)=a^62; 10) (a^62)*а=a^63; 11)(a^63)*(a^63)=a^126; 12) (a^126)*а=a^127; 13)(a^127)*(a^127)=a^254; 14) (a^7)*а=a^255; 11.2 - 11.3 1)а*а=a^2; 2)(a^2)*(a^2)=a^4; 3)(a^4)*a=a^5; - сохраняем a^5 4) (а^5)*(а^5)=a^10; 5)(a^10)*(a^5)=a^15; - вместо a^5 сохраняем a^15 6)(a^15)*(a^15)=a^30; 7)(a^30)*(a^30)=a^60; 8) (a^60)*(а^60)=a^120; 9)(a^120)*(a^120)=a^240; 10) (a^240)*(а^15)=a^255;