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

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

Идея рекурсивного решения заключается в разбиении задачи на два этапа: сначала считаем количество программ, которые приводят число 1 к числу 9, затем — от числа 9 к числу 15. Это нужно, чтобы учесть условие, что траектория содержит число 9.

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

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

- Если x > y, дальнейшие преобразования невозможны, возвращаем 0.

- Иначе вызываем функцию рекурсивно для всех возможных команд: x + 1, x + 3, x * 2 и суммируем результаты.

Затем для учета условия про число 9 перемножаем результаты двух вызовов функции: f(1, 9) * f(9, 15).

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

# Вычисляем количество программ, проходящих через число 9:
# сначала от 1 до 9, затем от 9 до 15
print(f(1, 9) * f(9, 15))

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

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

- Инициализируем массив нулями: a = [0] * 16, так как нас интересуют числа от 1 до 15.

- Задаем a[1] = 1, так как стартуем с числа 1, существует ровно один способ быть в этом состоянии.

- Перебираем все числа от 2 до 15 включительно:

   - Для числа i добавляем количество программ, которые приходят из i-1 командой «прибавить 1».

   - Добавляем количество программ из i-3 командой «прибавить 3».

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

- Чтобы учесть условие, что траектория содержит число 9, после обработки i == 9 обнуляем все предыдущие значения массива a[j] для j < 9, так как они не учитывают прохождение через число 9.

После прохода по массиву, a[15] содержит количество программ, удовлетворяющих всем условиям.

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

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