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

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

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

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

2. Если текущее число больше , то дальнейшие команды приведут только к превышению , поэтому возвращаем , так как такие пути не подходят.

3. Если ни одно из условий не выполнено, мы рекурсивно считаем все возможные пути из текущего числа: прибавляем 1, прибавляем 4, умножаем на 3, и суммируем количество полученных программ.

Так как траектория должна содержать число 18, мы делим вычисление на два этапа: сначала считаем все пути от 2 до 18, затем все пути от 18 до 35. Произведение этих двух значений даёт общее количество программ.

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

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

—

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

Мы создаём массив a размером 36 (чтобы индекс соответствовал числу от 0 до 35). Каждая ячейка массива будет хранить количество способов попасть в это число из числа 2, учитывая только допустимые команды.

1. Инициализируем массив нулями.

2. Устанавливаем a[2] = 1, так как начинаем с числа 2, существует один способ быть в этом положении.

3. Для каждого числа от 3 до 35 включительно:

- Считаем количество способов добраться до из командой "прибавить 1".

- Добавляем количество способов из командой "прибавить 4 если .

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

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

После заполнения массива, значение a[35] будет равно количеству программ, которые из числа 2 приводят к числу 35 и содержат число 18 в траектории.

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

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