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

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

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

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

2. Если текущее число больше или равно запрещённому числу 24, путь невозможен, возвращаем .

3. В остальных случаях мы применяем все возможные команды:

- n + 1, что соответствует команде «прибавить 1»;

- n * 3, что соответствует команде «умножить на 3»;

После чего суммируем результаты рекурсивных вызовов для этих двух вариантов.

Таким образом, вызов функции f(3, 36) рекурсивно переберёт все допустимые последовательности команд и вернёт общее количество программ.

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

# Запускаем функцию от 3 до 36 и выводим результат
print(f(3, 36))

—

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

Мы можем решить задачу динамически, создав массив a, где индекс соответствует числу, а значение по этому индексу — количество программ, которые приводят к этому числу.

1. Сначала создаём массив длиной 37 (чтобы включить число 36), все элементы равны 0.

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

3. Перебираем числа от 4 до 36. Для каждого числа :

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

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

- Если равно 24, обнуляем значение, так как траектория не должна содержать это число.

В результате, значение a[36] будет содержать количество всех программ, которые из числа 3 приводят к числу 36 без прохождения через 24.

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

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