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

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

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

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

def f(a, b, c): # a - начальное число, b - конечное, c - текущее число команд
    if a == b: # Если начальное число равно конечному, то вывести 1
        return 1
    if a > b: # Если начальное число больше конечного, то вывести 0
        return 0
    # Проверка того, что первая команда не 3 и не 5
    if c == 2 or c == 4:
        return f(a * 2, b, c + 1) + f(a * 2 + 1, b, c + 1)
    else:
        return f(a + 1, b, c + 1) + f(a * 2, b, c + 1) + f(a * 2 + 1, b, c + 1)
print(f(10, 68, 0))