23.03 Количество программ из A в B где траектория вычислений содержит число(-а)

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

Мы будем использовать рекурсивный подход, создавая функцию f(x, y), которая подсчитывает количество способов из числа получить число . Основная идея заключается в том, что мы рассматриваем все возможные последовательности команд и суммируем количество корректных программ. Для реализации мы разбиваем задачу на три этапа: из 3 в 9, из 9 в 11, из 11 в 13. Для каждого этапа функция работает одинаково:

- Если текущее число совпало с целевым , значит мы нашли один корректный путь, возвращаем 1.

- Если текущее число стало больше , значит дальнейшие действия не приводят к результату, возвращаем 0.

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

   Прибавить 1: f(x + 1, y)

   Прибавить 2: f(x + 2, y)

   Умножить на 2: f(x * 2, y)

В конце мы перемножаем результаты трех этапов, чтобы учесть обязательное прохождение чисел 9 и 11, так как каждый путь из предыдущего этапа можно соединить с любым путем следующего этапа.

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

# Перемножаем количество программ для каждого этапа,
# чтобы учесть обязательное прохождение чисел 9 и 11
print(f(3, 9) * f(9, 11) * f(11, 13))

—

Решение динамикой

Мы также можем посчитать количество программ с помощью динамического программирования. Для этого создаем массив a длиной достаточной, чтобы включить все числа до 13. Элементы массива будут хранить количество программ, приводящих к каждому числу. Мы идем по массиву от исходного числа 3 к 13, учитывая команды:

- Для каждого числа , начиная с 4 до 13:

   - Добавляем количество программ для , так как можно прийти командой "прибавить 1"

   - Добавляем количество программ для , так как можно прийти командой "прибавить 2"

   - Если четное, добавляем количество программ для , так как можно прийти командой "умножить на 2"

Чтобы учесть обязательное прохождение чисел 9 и 11, мы после вычисления этих чисел обнуляем все предыдущие значения массива, так как пути, которые их не достигли, не подходят. В конце значение покажет общее количество корректных программ.

# Создаем массив для хранения количества программ для чисел до 100
a = [0] * 100
# В начальное число 3 записываем 1, только один способ быть в исходном положении
a[3] = 1

# Проходим числа от 4 до 13
for i in range(4, 14):
    # Суммируем количество программ из предыдущих чисел,
    # учитывая команды прибавить 1, прибавить 2 и умножить на 2
    a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2 == 0)
    # Если число равно 9 или 11, обнуляем все предыдущие значения,
    # чтобы пути обязательно проходили через это число
    if i == 9 or i == 11:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих от 3 к 13 с обязательным прохождением 9 и 11
print(a[13])