Последние новости
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 Результат последней операции будем хранить в b. За одно умножение можно или увеличить степень на один(т е домножить на a), или увеличить степень в 2 раза(т е b*b). 1-->2-->3-->6-->7-->14-->15-->30-->31-->62-->63-->126-->127-->254-->255 14 стрелочек означают 14 операций умнодения. Где степень увеличилась на 1 нужно b=b*a, где степень увеличилась в 2 раза нужно b=b*b 11.2 1) b=a*a 2)b=b*b 3)b=b*b 4)b=b*b 5)b=b*a k=b 6)b=b*k 7)b=b*k k=b 8)b=b*b t=b 9)b=b*t 10)b=b*k 1-->2-->4-->8-->16-->17-->34-->51-->102-->204-->255