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

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

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

1. Если текущее число стало больше или равно запрещённому числу 25, значит этот путь недопустим, и функция возвращает 0.

2. Если совпало с , значит мы нашли корректную программу, и функция возвращает 1.

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

Поскольку траектория должна содержать число 12, мы делим задачу на два этапа: от 3 до 12 и от 12 до 96. Общее количество программ равно произведению количества программ каждого этапа, так как для каждого пути из первой части можно выбрать любой путь из второй части.

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

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

—

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

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

1. Инициализируем массив нулями.

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

3. Перебираем числа i от 4 до 96 включительно и для каждого числа:

- Добавляем a[i-3], чтобы учесть команду "прибавить 3".

- Если число делится на 2, добавляем a[i//2], чтобы учесть команду "умножить на 2".

- Вычисляем кубический корень числа i, если его куб равен i, добавляем a[x], чтобы учесть команду "возвести в третью степень".

4. Если i == 12, обнуляем все предыдущие значения a[j] для , так как траектория должна содержать число 12.

5. Если i == 25, обнуляем a[i], чтобы исключить запрещённое число из траектории.

В конце a[96] содержит количество программ, которые из числа 3 приводят к числу 96 с учётом всех условий.

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