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

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

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

1. Проверяем, достигли ли мы цели: если , значит путь завершён успешно, возвращаем .

2. Проверяем условие выхода за пределы: если , дальнейшие операции приведут к числу больше цели, возвращаем .

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

- прибавление 1 (x + 1),

- прибавление 4 (x + 4),

- умножение на 2 (x * 2),

и суммируем результаты этих вызовов.

Так как траектория должна содержать число 22, мы разбиваем задачу на два этапа: подсчёт программ от 4 до 22 и от 22 до 27. Итоговое количество программ равно произведению результатов этих двух этапов, так как каждый путь до 22 может сочетаться с любым путём от 22 до 27.

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

# Считаем количество программ от 4 до 22 и от 22 до 27, перемножаем результаты
print(f(4, 22) * f(22, 27))

—

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

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

1. Инициализируем массив нулями и ставим a[4] = 1, так как начинаем с числа 4, и существует один способ находиться на нём.

2. Перебираем числа от 5 до 27 включительно. Для каждого числа :

- добавляем количество программ, ведущих из , для команды "прибавить 1

- добавляем количество программ, ведущих из , для команды "прибавить 4

- если чётное, добавляем количество программ из , для команды "умножить на 2".

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

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

# Создаем массив длиной 28, заполняем нулями
a = [0] * 28
# Начальное положение: только один способ быть в числе 4
a[4] = 1
# Перебираем числа от 5 до 27 включительно
for i in range(5, 28):
    # Суммируем количество программ, ведущих из i-1 и i-4
    # Для i четного добавляем путь из i//2
    a[i] = a[i - 1] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 22, обнуляем все предыдущие значения
    # чтобы учесть обязательное прохождение через 22
    if i == 22:
        for j in range(i):
            a[j] = 0

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