Question

Вы хотите возвести данное число 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).
Чем меньше операций умножения вы будете использовать, тем больше баллов вы получите, при условии, что предложенные последовательности вычисления степеней являются корректными.
25 баллов

Answer 1

Программа на python 3, перебирающая все возможные последовательности определённой длины:
def shortest_chains(n):
  def next_chains(chain):
    new_elems = set()
    for i in range(len(chain)):
      for j in range(i, len(chain)):
        new_elem = chain[i] + chain[j]
        if new_elem > chain[-1] and new_elem not in new_elems:
          new_elems.add(new_elem)
          yield chain + [new_elem]
  
  current_stage = None
  next_stage = [[1]]
  answer = []
  while len(answer) == 0:
    current_stage = next_stage
    next_stage = []
    for chain in current_stage:
      next_stage.extend(next_chains(chain))
    answer = [chain[1:] for chain in next_stage if chain[-1] == n]
  return answer
    
def print_solution(n):
  answer = shortest_chains(n)
  print("Для {} есть {} решений(-я, -е):".format(n, len(answer)))
  for i in range(len(answer)):
    print("{}. {}".format(i + 1, " ".join(map(str, answer[i]))))
  print()

Запустив, можно получить все 5 возможных решений для числа 7, по 4 решения для 15 и 23 и 87 решений для 63.

e5e9c4ff074d8b2fa1510cb5bb6e4862.txt