23.01 Количество программ из A в B

Решение рекурсией

Определим функцию f(a, b, mult), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (+1, умножить на 2, +2, умножить на 4), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

def f(a, b, mult): # а - начальное число, b - конечное, mult - количество умножений
  # Если начальное число равно конечному и число команд умножения меньше или равно 2, вывести 1
  if a == b and mult <= 2:
    return 1
  # Если начальное число больше конечного, вывести 0
  if a > b:
    return 0
    # Если две команды умножения, то выполнять только сложение
  if mult == 2:
    # Выполнение основных команд (исключаем умножение, поскольку три раза подряд оно идти не может)
    return f(a + 1, b, mult) + f(a + 2, b, mult)
  # Выполнение основных команд
  return f(a + 1, b, mult) + f(a + 2, b, mult) + f(a * 2, b, mult + 1)+ f(a * 4, b, mult + 1) # Выполнение основных команд
print(f(1, 13, 0)) # Наш ответ