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

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

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

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

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

3. В остальных случаях функция вызывает саму себя трижды, соответствуя трём командам:

- f(x + 3, y) — прибавить 3;

- f(x + 4, y) — прибавить 4;

- f(x * 2, y) — умножить на 2.

Суммируем результаты этих вызовов, чтобы получить общее количество программ.

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

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

# Вычисляем общее количество программ, проходящих через число 22
# Сначала количество программ от 3 до 22
# Потом количество программ от 22 до 35
# Произведение этих чисел даст итоговое количество
print(f(3, 22) * f(22, 35))

—

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

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

1. Создаём массив a размера 36, заполненный нулями. Каждая ячейка a[i] хранит количество программ, приводящих к числу .

2. В ячейку a[3] записываем 1, так как начинаем с числа 3.

3. Для всех чисел от 4 до 35 считаем количество программ:

- a[i] = a[i-3] + a[i-4] + a[i//2] * (i % 2 == 0) — учитываем команды "прибавить 3 "прибавить 4"и "умножить на 2"(умножение возможно только для чётных чисел).

4. Когда достигаем числа 22, обнуляем все предыдущие значения массива (a[j] = 0 для всех ), чтобы гарантировать, что траектория проходит через 22.

5. После завершения цикла элемент a[35] содержит количество программ, которые приводят от 3 к 35 через число 22.

# Создаем массив размера 36 и заполняем нулями
a = [0] * 36
# Начальное число 3, только один способ быть в этом состоянии
a[3] = 1

# Перебираем все числа от 4 до 35 и считаем количество программ
for i in range(4, 36):
    # Команда прибавить 3
    a[i] = a[i - 3] + a[i]
    # Команда прибавить 4
    a[i] += a[i - 4]
    # Команда умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        a[i] += a[i // 2]

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

# Результат: количество программ от 3 до 35 через 22
print(a[35])