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

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

Заполним таблицу по данной формуле до 7:

По условию сказано, что траектория должна содержать число 8, значит , так как число 9 можем получить только первой командой.

Продолжим заполнять таблицу:

В условии сказано, что траектория не содержит число 14. Значит .

Заполним таблицу до конца:

Отсюда получаем ответ — 840.

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

Мы решаем задачу рекурсивно, строя функцию f(x, y), которая подсчитывает количество программ, преобразующих число в число , учитывая все условия задачи.

1. Сначала мы проверяем, нарушает ли текущее число условия задачи: - если текущее число превысило целевое число , дальнейшие шаги невозможны, возвращаем 0; - если текущее число равно запрещённым значениям (например, 14, которое не должно встречаться в траектории), путь недопустим, возвращаем 0.

2. Если текущее число совпало с целевым числом , значит, мы нашли корректную программу, возвращаем 1.

3. В остальных случаях считаем все возможные варианты продолжения программы: - прибавляем 1 к числу и вызываем рекурсию; - прибавляем 2 к числу и вызываем рекурсию; - суммируем результаты этих вызовов, чтобы получить общее количество программ, ведущих от к .

4. Так как траектория должна содержать число 8, но не содержать число 14, мы делим задачу на два этапа: - первый этап: от 1 до 8 с проверкой запрета числа 14; - второй этап: от 8 до 19 с проверкой запрета числа 14; - общее количество программ равно произведению результатов двух этапов, так как для каждого пути первой части можно использовать любой путь второй части.

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число больше целевого или равно запрещённому числу (14),
    # путь невозможен, возвращаем 0
    if x > y or x == 14:
        return 0
    # Если текущее число совпало с целевым,
    # найден корректный путь, возвращаем 1
    if x == y:
        return 1
    # В остальных случаях пробуем оба варианта команд:
    # прибавить 1 и прибавить 2, и суммируем результаты
    return f(x + 1, y) + f(x + 2, y)

# Вычисляем количество программ с учётом условия траектории:
# первый этап: от 1 до 8
# второй этап: от 8 до 19
# Общее количество программ равно произведению двух этапов
print(f(1, 8) * f(8, 19))