Задание 23. Способ 2

"""
Первый способ. Задом на перед

Через этот способ мы идем от результирующего числа к исходному.
Наша функция отвечает на вопрос "сколько существует комманд от 2-х до n.

Плюсы:
+ похож на решение руками

Минусы:
- дольше писать
- больше условий, которые надо учитывать (делится ли на 3, например)
"""

A = 2  # исходное число
B = 72  # результирующее число

def F(n):
    # тут пишем плохие случаи. Либо мы убежали далеко за исходное число, либо мы сейчас
    # на том числе, которое должны избегать
    if n < A or n == 12 or n == 24:
        return 0

    # если мы стоим ровно на исходном числе
    if n == A:
        return 1

    # если мы можем произвести операцию деления на 3
    if n % 3 == 0:
        return F(n - 1) + F(n // 3)

    # в противном случае мы не можем произвести операцию деления на 3 - пропускаем ее
    return F(n - 1)

# вычисляем, сколько программ сузествует от 2-х до B
print(F(B))