• 
  • 08 January 2021
  Информатика
  • Автор: Yarik150220031

  

  Вы хотите возвести данное число 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 баллов

• 
  • 08 January 2021
  • Ответ оставил: nelle987

  Программа на 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.

  0
• 
  • НЕ НАШЛИ ОТВЕТ?

  Если вас не устраивает ответ или его нет, то попробуйте воспользоваться поиском на сайте и найти похожие ответы по предмету школьной программы: информатика.
  На сегодняшний день (23.01.2026) наш сайт содержит 109576 вопросов, по теме: информатика. Возможно среди них вы найдете подходящий ответ на свой вопрос.

  Найти другие ответы
• Нажимая на кнопку "Ответить на вопрос", я даю согласие на обработку персональных данных

  Ответить на вопрос

Последние опубликованные вопросы