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

Пусть — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу по данным формулам до 10:

По условию сказано, что траектория должна проходить через число 10, значит , так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:

Отсюда получаем ответ — 243.

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

Идея решения заключается в использовании рекурсивной функции для подсчёта количества программ, преобразующих число в число . Мы рассматриваем все возможные действия на каждом шаге и суммируем количество способов, которые они дают. Так как траектория должна содержать число 10, решение разделяем на два этапа: сначала от 2 до 10, затем от 10 до 17, а итоговое количество программ равно произведению результатов обоих этапов.

Внутри функции проверяются условия:

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

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

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

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

# Считаем количество программ, которые проходят через 10
# сначала от 2 до 10, затем от 10 до 17, результат перемножаем
print(f(2,10) * f(10,17))