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

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

Мы решаем задачу рекурсивно, создавая функцию f(x, y), которая считает количество программ, преобразующих число в число . 1. Сначала проверяем, нарушает ли текущее число условие задачи: - Если , то дальнейшие преобразования уже не приведут к числу , поэтому возвращаем 0. - Если , то траектория запрещена по условию задачи, возвращаем 0. 2. Проверяем, достигли ли мы цели: - Если , значит найден один корректный путь, возвращаем 1. 3. Если ни одно из условий не выполнено, считаем все возможные переходы из текущего числа: - Прибавляем 1 и вызываем f(x + 1, y) - Умножаем на 2 и вызываем f(x * 2, y) - Умножаем на 3 и вызываем f(x * 3, y) - Складываем результаты всех трёх вызовов, чтобы получить общее количество программ.

Так как по условию траектория должна содержать число 14, но не содержать число 16, мы делаем два независимых вызова функции: f(1, 14) и f(14, 50), а затем перемножаем результаты, так как каждый путь из первой части можно соединить с любым путем из второй части.

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

# Вычисляем количество программ от 1 до 14 и от 14 до 50
# и перемножаем результаты, так как траектория должна проходить через 14
print(f(1, 14) * f(14, 50))

—

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

Мы решаем задачу динамическим способом, создавая массив a длиной 51 (для чисел от 0 до 50), где a[i] хранит количество программ, которые преобразуют число 1 в число .

1. Инициализируем массив нулями: a = [0]*51 2. Задаём начальное положение: a[1] = 1, так как изначально мы находимся в числе 1. 3. Перебираем числа от 2 до 50: - Для каждого числа i добавляем количество программ, ведущих в i из i-1 (команда +1): a[i] = a[i-1] - Если i делится на 2, добавляем количество программ, ведущих в i из i//2 (команда *2): a[i] += a[i//2] - Если i делится на 3, добавляем количество программ, ведущих в i из i//3 (команда *3): a[i] += a[i//3] - Если i = 14, нужно сбросить все значения для чисел меньше 14, так как траектория до 14 должна быть из 1 без промежуточного попадания в запрещенные числа: for j in range(14): a[j] = 0 - Если i = 16, обнуляем a[i] по условию запрета на число 16: a[i] = 0

4. После прохода по всем числам a[50] содержит количество программ от 1 до 50 с учётом всех условий.

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

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