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

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

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

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

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

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

Так как требуется, чтобы траектория обязательно проходила через число 30, общее количество программ вычисляется как произведение f(12, 30) и f(30, 96).

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

# Вычисляем и выводим общее количество программ,
# проходящих через число 30
print(f(12, 30) * f(30, 96))

—

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

Идея динамического подхода состоит в том, чтобы создать массив a, где индекс соответствует числу, а значение по индексу — количество способов добраться до этого числа из числа 12.

1. Создаём массив длиной 97, изначально заполненный нулями, и записываем в ячейку с индексом 12 значение 1, так как стартуем с числа 12.

2. Проходим циклом по всем числам от 15 до 96 включительно. Для каждого числа :

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

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

3. После того как мы дошли до числа 30, обнуляем все значения до 30, так как траектория должна обязательно проходить через 30, и предыдущие пути нельзя учитывать.

4. После заполнения массива, значение в ячейке с индексом 96 будет равно количеству программ, удовлетворяющих условию задачи.

# Создаем массив длиной 97, все элементы изначально равны 0
a = [0]*97
# В ячейку с индексом 12 записываем 1, так как стартуем с числа 12
a[12] = 1
# Перебираем числа от 15 до 96 включительно
for i in range(15, 97):
    # Количество способов добраться до i увеличиваем на:
    # a[i-3] - путь командой "прибавить 3"
    # a[i//2] * (i % 2 == 0) - путь командой "умножить на 2", только если i четное
    a[i] += a[i-3] + a[i//2] * (i % 2 == 0)
    # Если достигли числа 30, обнуляем все предыдущие значения,
    # так как траектория должна обязательно проходить через 30
    if i == 30:
        for j in range(30):
            a[j] = 0

# Выводим количество программ, которые приводят от 12 к 96,
# проходя через 30
print(a[96])