23.06 Количество программ из A в B где траектория вычислений N команда

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

Мы используем рекурсивный подход, который заключается в построении функции f(a, c), где: 1. a — текущее число на экране. 2. c — количество использованных команд.

Идея решения: на каждом шаге мы проверяем, достигли ли мы максимального количества команд. Если c == 7, то проверяем, равно ли текущее число a целевому числу 27. Если да, возвращаем 1 (найден подходящий путь), если нет — 0.

Если количество команд меньше 7, то мы пробуем применить каждую из трёх команд и рекурсивно вызываем функцию с обновлёнными значениями: - Используем команду "прибавить 1 увеличиваем c на 1. - Используем команду "прибавить 4 увеличиваем c на 1. - Используем команду "умножить на 2 увеличиваем c на 1.

Результаты этих трёх рекурсивных вызовов суммируются, чтобы получить общее количество программ, которые из числа 3 после 7 команд приводят к числу 27.

# Определяем рекурсивную функцию f(a, c)
# a - текущее число на экране
# c - количество использованных команд
def f(a, c):
    # Если использовано 7 команд, проверяем, достигли ли цели
    # Возвращаем 1, если a равно 27, иначе 0
    if c == 7:
        return a == 27
    # В остальных случаях пробуем все три команды:
    # 1) прибавляем 1 к числу и увеличиваем c на 1
    # 2) прибавляем 4 к числу и увеличиваем c на 1
    # 3) умножаем число на 2 и увеличиваем c на 1
    # Складываем количество программ для всех вариантов
    return f(a + 1, c + 1) + f(a + 4, c + 1) + f(a * 2, c + 1)

# Запускаем функцию от исходного числа 3 и нулевого количества команд
# Выводим общее количество программ, приводящих к числу 27
print(f(3, 0))