23.02 Количество программ из A в B (на убывание)

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

Идея рекурсивного решения заключается в том, чтобы построить функцию, которая считает количество всех программ, преобразующих число в число . Функция работает следующим образом: если текущее число равно целевому числу , значит найден один корректный путь, и функция возвращает 1; если текущее число меньше , значит дальнейшие операции невозможны и путь недопустим, функция возвращает 0; в остальных случаях функция вызывает саму себя дважды: первый вызов с аргументом , что соответствует команде «разделить на 2», второй вызов с аргументом , что соответствует команде «вычесть 1». Результаты этих вызовов суммируются, чтобы получить общее количество программ. Вызов функции f(64,14) рекурсивно перебирает все варианты команд, подсчитывая все возможные последовательности от 64 до 14.

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

# Запускаем функцию от 64 до 14 и выводим результат
print(f(64, 14))

—

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

Динамический способ решения строится на том, что мы создаем массив, где каждый индекс соответствует числу, а значение по этому индексу показывает количество способов преобразовать 64 в число . Изначально создаем массив из 65 элементов (от 0 до 64) и присваиваем , так как стартуем с числа 64 и существует ровно один способ быть в этом положении. Затем проходим по массиву от 64 вниз до 15, для каждого числа распределяя его количество способов на два числа, в которые можно перейти: (команда «разделить на 2») и (команда «вычесть 1»), суммируя к уже существующим значениям. После завершения цикла в хранится общее количество программ, преобразующих 64 в 14.

# Создаем массив для хранения количества программ для чисел от 0 до 64
a = [0] * 65
# Начальное число 64, количество способов быть в нём равно 1
a[64] = 1
# Проходим по всем числам от 64 вниз до 15
for i in range(64, 14, -1):
    # Для каждого числа i распределяем количество способов
    # на число i//2 (разделить на 2) и i-1 (вычесть 1)
    a[i // 2] += a[i]
    a[i - 1] += a[i]

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