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

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

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

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

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

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

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

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

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

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

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

# Вычисляем количество программ: сначала от 3 до 12, затем от 12 до 20
print(f(3, 12) * f(12, 20))

—

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

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

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

2. Устанавливаем стартовое положение: a[3] = 1, так как начинаем с числа 3.

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

- добавляем количество способов, приходящих из i-1 и i-3 (команды +1 и +3): a[i] = a[i-1] + a[i-3]

- если i делится на 4, учитываем команду умножить на 4: if i % 4 == 0: a[i] += a[i//4]

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

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

После завершения цикла a[20] содержит количество программ, которые преобразуют 3 в 20, проходя через 12 и не содержат 7.

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