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

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

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

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

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