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

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

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

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

def f(a, b, two): # two - число цифр 2 в последовательности действий
  # Подсчёт количества цифр 2
  if "2" in str(a):
    two += 1
  # Если начальное число равно конечному и число цифр 2 меньше или равно 1, вывести 1
  if a == b and two <= 1:
    return 1
  # Если начальное число больше конечного и число цифр 2 больше 1, вывести 0
  if a > b or two > 1:
    return 0
  # Выполнение основных команд
  return f(a + 1, b, two) + f(a + 3, b, two) + f(a * 2, b, two)+ f(a * 5, b, two)
print(f(6, 38, 0)) # Наш ответ