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

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

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

1. Если текущее число больше целевого числа , значит путь невозможен, возвращаем 0.

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

3. Если ни одно из условий не выполнено, то считаем все возможные переходы из текущего числа:

- прибавляем 1, вызываем f(a + 1, b);

- прибавляем 2, вызываем f(a + 2, b);

- умножаем на 3, вызываем f(a * 3, b);

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

Так как по условию траектория должна содержать число 9, мы разбиваем задачу на два этапа:

- Первый этап: от 3 до 9, считаем количество способов дойти до 9.

- Второй этап: от 9 до 14, считаем количество способов дойти до 14, начиная с 9.

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

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

# Вычисляем количество программ от 3 до 14 через число 9
print(f(3, 9) * f(9, 14))

—

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

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

1. Создаем массив a длиной 15 (так как максимальное число 14) и заполняем нулями.

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

3. Перебираем числа от 4 до 14 включительно:

- Для числа i считаем количество программ из предыдущих чисел:

* из i-1, прибавив 1;

* из i-2, прибавив 2;

* из i//3, если i делится на 3, умножив на 3.

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

Итоговое количество программ, которые ведут от 3 к 14 через число 9, хранится в a[14].

# Создаем массив для хранения количества программ до каждого числа
a = [0] * 15
# Инициализируем исходное число 3
a[3] = 1
# Перебираем все числа от 4 до 14
for i in range(4, 15):
    # Считаем количество программ через предыдущие числа
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Обнуляем предыдущие значения до числа 9, чтобы траектория обязательно содержала 9
    if i == 9:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые ведут от 3 к 14 через число 9
print(a[14])