Вы хотите возвести данное число a в некоторую целочисленную степень n, но ваш калькулятор умеет только перемножать числа. Например, вы можете вычислить a2 = a × a, затемвыможетевычислитьa3 =a2 ×aилиa4 =a2 ×a2.
Вы можете по-разному организовать вычисление значения an. Например, вычислить a5 можно за 4 умножения:
1) a2 = a × a, 2) a3 = a2 × a, 3) a4 = a3 × a, 4) a5 = a4 × a.
Но можно вычислить a5 всего лишь за 3 умножения: 1) a2 = a × a,
2) a3 = a2 × a, 3) a5=a3×a2.
Вам необходимо определить, за какое минимальное число умножений можно вычислить следующие степени: 7, 15, 23, 63. Вычисление каждой из этих степеней должно быть независимо от остальных, то есть при вычислении 15-й степени нельзя использовать вычисления, проделанные ранее для вычисления 7-й степени. Вы решаете четыре независимые задачи – за какое минимальное число умножений можно вычислить 7-ю степень, 15-ю степень, 23-ю степень и 63-ю степень.
Ответ на это задание записывается в четырёх строках. Каждая строка должна содержать последовательность вычисления каждой из указанных степеней. Первая строка должна содержать последовательность вычисления 7-й степени, вторая строка – 15-й степени, третья строка – 23-й степени, четвертая строка – 63-й степени.
Каждая строка содержит через пробел несколько целых чисел – значения степеней в том порядке, в котором они вычисляются. Например, для вычисления 5-й степени решение можно записать в виде строки
23 5или
2 4 5,
что означает, что последовательно вычисляются степени a2, a3, a5 (одно возможное решение) или a2, a4, a5 (другое возможное решение). Такм образом, каждая строка должна начинаться числом 2, а заканчиваться тем значением степени, которое нужно вычислить (7, 15, 23, 63).
Чем меньше операций умножения вы будете использовать, тем больше баллов вы получите, при условии, что предложенные последовательности вычисления степеней являются корректными.
50 баллов