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

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

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

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

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

3. Если ни одно из условий не выполнено, значит ещё можно применять команды, поэтому делаем три рекурсивных вызова функции:

- первый вызов с аргументом , что соответствует команде A "прибавить 1";

- второй вызов с аргументом , что соответствует команде C "умножить на 2";

- третий вызов с аргументом , что соответствует команде B "прибавить 4".

Так как траектория должна содержать число 18, мы разделяем вычисления на два этапа: от 10 до 18 и от 18 до 36. Результаты двух этапов перемножаются, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

# Вычисляем количество программ от 10 до 18 и от 18 до 36, умножаем результаты
print(f(10, 18) * f(18, 36))

—

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

Решение кодом через динамику заключается в том, что мы создаём массив a длиной 37 элементов (так как целевое число 36) и заполняем его нулями. Каждый индекс массива соответствует числу, а значение в ячейке показывает количество программ, которые приводят от исходного числа 10 к этому числу.

1. В ячейку с индексом 10 записываем 1, так как существует ровно один способ быть в исходном числе.

2. Для каждого числа от 11 до 36:

- Считаем количество программ, которые приходят из (команда A), из (команда B) и из , только если чётное (команда C).

- Если равно 18, то обнуляем все предыдущие значения массива (от 0 до 17), так как траектория должна содержать число 18, и все пути, не достигшие этого числа, больше не считаются.

После прохода по массиву значение в a[36] даёт итоговое количество программ.

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

# Выводим количество программ, которые ведут от 10 к 36, через 18
print(a[36])