23.02 Количество программ из A в B (на убывание)

Рекурсия:

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

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

- Сначала проверяем, не стало ли число меньше целевого. Если , то дальнейшее применение команд приведет к числам меньше , поэтому путь невозможен, возвращаем .

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

- Если ни одно из условий не выполнено, вызываем функцию рекурсивно трижды, соответствуя трем командам:

1. x-3 — уменьшение на 3

2. x-5 — уменьшение на 5

3. x//3 — целая часть от деления на 3

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

Так как траектория должна проходить через числа 68 → 35 → 14 → 4, общее количество программ вычисляется как произведение трёх рекурсивных вызовов: f(68, 35) * f(35, 14) * f(14, 4).

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

# Вычисляем количество программ, проходящих через все ключевые числа: 68 -> 35 -> 14 -> 4
print(f(68, 35) * f(35, 14) * f(14, 4))

—

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

Динамический подход заключается в том, чтобы создать массив, где индекс соответствует числу на экране, а значение хранит количество способов добраться до этого числа.

1. Создаем массив a длиной достаточно большой, чтобы покрыть все числа от исходного до целевого, и заполняем его нулями.

2. В ячейку с индексом 68 записываем 1, так как начинаем с числа 68 и существует ровно один способ находиться в этом состоянии.

3. Проходим по массиву в обратном порядке от 68 до 4:

- Если текущий индекс равен 14 или 35, обнуляем все предыдущие ячейки, чтобы учесть условие, что траектория должна пройти через эти числа.

- Для каждого числа добавляем его значение в ячейки, соответствующие результатам применения команд:

- i - 3

- i - 5

- i // 3

4. После прохода по всем значениям, ячейка a[4] содержит общее количество программ, ведущих от 68 к 4 с учётом прохождения через 35 и 14.

# Создаем массив для подсчета количества программ, все элементы инициализируем нулями
a = [0] * 1000
# В ячейку с индексом 68 записываем 1, стартуем с числа 68
a[68] = 1
# Проходим по всем числам от 68 до 4 включительно, двигаясь вниз
for i in range(68, 3, -1):
    # Если текущий индекс 14 или 35, обнуляем все ячейки ниже текущей,
    # чтобы траектория учитывала прохождение через эти числа
    if i == 14 or i == 35:
        for j in range(i):
            a[j] = 0
    # Применяем команды и суммируем количество программ для соответствующих чисел
    a[i - 3] += a[i]
    a[i - 5] += a[i]
    a[i // 3] += a[i]

# Выводим общее количество программ, ведущих к числу 4
print(a[4])