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

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

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

- Функция принимает три аргумента: — текущее число, — целевое число, — логическая переменная, которая отмечает, достигнуто ли число 9.

- На каждом шаге проверяем условия:

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

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

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

- В остальных случаях функция рекурсивно вызывает себя трижды: (команда 1), (команда 2), (команда 3). Сумма этих вызовов дает общее количество программ для текущего состояния.

Вызов функции f(3, 14) запускает рекурсивный перебор всех возможных последовательностей команд, проходящих через число 9.

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

# Запуск функции с начальным числом 3 и целевым числом 14
print(f(3, 14))

—

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

Идея динамического решения заключается в последовательном вычислении количества программ для каждого числа от начального до целевого с учетом условия прохождения через число 9.

- Создаем массив a длиной 15 (чтобы включить число 14), изначально все элементы равны 0.

- Начальное положение: a[3] = 1, так как существует ровно один способ быть в числе 3.

- Для чисел от 4 до 9 заполняем массив:

1. a[i] += a[i-1] — добавляем количество программ, приведших к командой +1.

2. a[i] += a[i-2] — добавляем количество программ, приведших к командой +2.

3. Если делится на 3, a[i] += a[i//3] — добавляем количество программ, пришедших командой *3.

- После заполнения чисел до 9 обнуляем все элементы массива с индексами от 1 до 8, так как траектория должна содержать число 9, и пути, которые не проходят через 9, больше не учитываются.

- Для чисел от 10 до 14 повторяем процесс суммирования значений для переходов +1, +2 и *3.

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

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