№ 2308. Авторские варианты - ЕГЭ по информатике

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены буквами:

A. Вычесть 1

B. Умножить на 2
C. Умножить на 3

Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 17, и при этом не содержат двух команд A подряд?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAC при исходном числе 2 траектория будет состоять из чисел 4, 3, 9.

Ответ
Python

def f(x, y, A=0):
    if x == y:
        return 1
    if x > y + 1:
        return 0
    if A == 1:
        return (f(x * 2, y) +
                f(x * 3, y))

    return (f(x - 1, y, 1) +
            f(x * 2, y) +
            f(x * 3, y))


print(f(3, 17))