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

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

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

1. Аргументы функции:

- s — список, содержащий последовательность чисел, полученных после применения команд. Последний элемент списка s[-1] является текущим числом на экране.

2. Логика работы функции:

- Получаем текущее число a = s[-1].

- Проверяем, достигнута ли цель: если длина списка больше 1 и текущее число равно 12, возвращаем 1 — найден подходящий путь.

- Проверяем корректность текущего числа:

- Если оно меньше 10 или больше 30, путь недопустим.

- Если текущее число уже встречалось в траектории (a in s[:-1]), путь недопустим.

- В этих случаях возвращаем 0.

- Если число корректное, рекурсивно вызываем функцию для всех трёх возможных команд:

- a + 2 — прибавить 2

- a + 1 — прибавить 1

- a - 3 — вычесть 3

- Суммируем результаты трёх рекурсивных вызовов, чтобы получить общее количество подходящих программ.

3. Запускаем рекурсию с исходного числа 20, помещенного в список [20].

4. Выводим результат.

# Рекурсивная функция для подсчета количества программ
def f(s):
    # Текущее число на экране — последний элемент последовательности
    a = s[-1]
    # Если достигли цели (12) и есть хотя бы одно число в траектории
    if len(s) > 1 and a == 12:
        return 1
    # Проверка, что число в допустимом диапазоне и не повторяется в траектории
    if a < 10 or a > 30 or (a in s[:-1]):
        return 0
    # Рекурсивно проверяем все три команды и суммируем результаты
    return sum(f(s + [a + h]) for h in [2, 1, -3])

# Запуск функции с исходного числа 20
print(f([20]))