23.05 Количество программ из A в B смешанное

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

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

1. Если текущее число x больше y или равно запрещённому числу 14, то дальнейшие преобразования невозможны, возвращаем 0.

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

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

- прибавить 1 (x + 1)

- прибавить 2 (x + 2)

- умножить на 3 (x * 3)

Итоговое количество программ, которые проходят через число 10 и не содержат 14, получается произведением f(2, 10) и f(10, 15), так как каждая траектория до 10 может соединяться с любой траекторией от 10 до 15.

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

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

—

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

Мы создаем массив a, где каждый индекс i соответствует числу на экране, а значение a[i] хранит количество программ, которые приводят к этому числу.

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

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

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

- добавляем количество способов из предыдущих чисел, если можно добраться командой +1 или +2: a[i] = a[i-1] + a[i-2]

- если i делится на 3, прибавляем количество способов, приходящих из i//3: if i % 3 == 0: a[i] += a[i//3]

- если i == 10, обнуляем все предыдущие значения, чтобы обеспечить прохождение через 10: for j in range(1, i): a[j] = 0

- если i == 14, запрещенное число, обнуляем a[i]

После завершения цикла a[15] содержит количество программ, которые преобразуют 2 в 15, проходя через 10 и не содержащие 14.

# Создаем массив для хранения количества программ для каждого числа
a = [0]*16
# Стартовое число 2 имеет ровно один способ
a[2] = 1
# Проходим по всем числам от 3 до 15
for i in range(3, 16):
    # Считаем количество программ, которые приходят из i-1 и i-2
    a[i] = a[i-1] + a[i-2]
    # Если число делится на 3, учитываем команду умножить на 3
    if i % 3 == 0:
        a[i] += a[i//3]
    # Обеспечиваем прохождение через число 10, обнуляем все предыдущие числа
    if i == 10:
        for j in range(1, i):
            a[j] = 0
    # Запрещенное число 14 обнуляем
    if i == 14:
        a[i] = 0
# Выводим количество программ, приводящих 2 к 15 с условием задачи
print(a[15])