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

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

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

Внутри функции мы проверяем следующие условия:

1. Если текущее число больше целевого числа или равно запрещённым числам 13 или 18, путь невозможен, возвращаем 0.

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

3. В противном случае считаем все возможные переходы: прибавляем 4, прибавляем 5 или умножаем на 2, вызывая функцию рекурсивно для каждого варианта и суммируя результаты.

Так как траектория должна содержать число 11, мы умножаем количество программ от 3 до 11 на количество программ от 11 до 23.

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

# Общее количество программ равно произведению числа программ от 3 до 11 и от 11 до 23
print(f(3, 11) * f(11, 23))

—

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

Мы используем динамический способ, создавая массив a длиной 24, где индекс соответствует числу на экране, а значение по индексу показывает количество программ, ведущих к этому числу.

1. Инициализируем массив нулями и записываем в a[3] = 1, так как начинаем с числа 3.

2. Перебираем числа от 4 до 23 и для каждого числа выполняем:

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

- Если равно 11, обнуляем все предыдущие элементы массива, так как число 11 должно быть включено в траекторию и предыдущие пути до него не учитываются.

- Если равно 13 или 18, обнуляем a[i], так как эти числа запрещены в траектории.

3. После прохода по всем индексам, количество программ, приводящих от 3 к 23 с учётом условий, хранится в a[23].

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

# Выводим количество программ, ведущих от 3 к 23 с учётом всех условий
print(a[23])

Решение аналитически

Составим формулы для решения этой задачи:

— если число не делится на 2.

— если число делится на 2.

Заметим, что число 3 мы получаем одним способом — пустой программой. Числа 4, 5 мы получить не можем данными командами. Заполним таблицу: