23.07 Количество результатов выполнения программ

Рекурсивное решение:

1. Введём рекурсивную функцию , где:

- — текущее число на экране,

- — целевое число,

- — номер команды, выполненной на предыдущем шаге.

2. Если , возвращаем 0 (превышено целевое число).

3. Если , возвращаем 1 (найдена программа, ведущая к цели).

4. Если предыдущая команда была вторая (), то следующий шаг обязательно третья команда:

5. В остальных случаях можно применить любую команду:

- (команда 1)

- (команда 2)

- (команда 3)

def f(a, b, c=0):
    # a - текущее число на экране
    # b - целевое число
    # c - номер команды, выполненной на предыдущем шаге (0 означает, что команды ещё не было)

    if a > b:
        # Если текущее число больше целевого, пути нет
        return 0

    if a == b:
        # Если текущее число равно целевому, найден один путь
        return 1

    if c == 2:
        # Если предыдущая команда была 2 (умножить на 2),
        # следующая обязательно должна быть команда 3 (умножить на 3)
        return f(a * 3, b, 3)

    # В остальных случаях можно применить любую из трёх команд:
    # 1. прибавить 1
    # 2. умножить на 2
    # 3. умножить на 3
    return f(a + 1, b, 1) + f(a * 2, b, 2) + f(a * 3, b, 3)

# Запускаем функцию с исходным числом 8, целевым числом 123
print(f(8, 123))