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

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

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

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

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

- Если текущее число равно 10, устанавливаем флаг flag=True, чтобы отметить достижение промежуточной цели.

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

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

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

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

# Запускаем функцию с начальным числом 2, целевым числом 13 и флагом False
print(f(2, 13, False))

—

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

Идея динамического решения заключается в последовательном заполнении массива, где каждый индекс соответствует числу, а значение — количеству программ, которые приводят от начального числа 2 к этому числу. При этом необходимо учитывать, что число 10 должно быть достигнуто.

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

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

- Для каждого числа от 3 до 13 последовательно вычисляем количество программ:

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

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

3. Если делится на 3, добавляем a[i//3] — количество программ, приведших к , если применить команду "умножить на 3".

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

- В конце массив a[13] содержит количество программ, которые приводят от 2 к 13, проходя через 10.

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

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