23.01 Количество программ из A в B

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

Идея решения с помощью рекурсии заключается в том, что мы определяем функцию, которая подсчитывает количество способов преобразовать число в число . Внутри функции задаём три условия: если текущее число превысило , то возвращаем , так как дальнейшие преобразования не имеют смысла; если совпало с , то возвращаем , так как найден корректный путь; если ни одно из этих условий не выполнено, то функция вызывает саму себя дважды — первый раз с аргументом (что соответствует команде "прибавить 2"), второй раз с аргументом (что соответствует команде "умножить на 3"). Таким образом, итоговое количество способов будет равно сумме результатов этих двух рекурсивных вызовов. Запуск функции с начальными значениями даст количество всех программ, которые из числа 7 приводят к числу 77.

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

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

—

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

Идея динамического подхода состоит в том, чтобы построить массив, где индекс соответствует числу, а значение по этому индексу показывает количество способов добраться до этого числа. Сначала заполняем массив нулями, а в ячейку с индексом 7 записываем 1, так как изначально мы находимся в числе 7, и существует ровно один способ быть в этом положении. Далее для каждого числа от 8 до 77 вычисляем количество способов добраться до него:

- если в можно попасть из командой "прибавить 2 то добавляем ; - если делится на 3, то в него можно попасть из командой "умножить на 3 и тогда добавляем ; - иначе такой переход невозможен.

Таким образом, при проходе по всем значениям последовательно мы получаем корректные значения для всех индексов массива, а итоговый ответ хранится в .

# Создаем массив из 80 элементов, все значения изначально равны 0
a = [0] * 80
# В ячейку с индексом 7 записываем 1, так как стартуем с числа 7
a[7] = 1
# Перебираем все числа от 8 до 77
for i in range(8, 78):
    # В число i можно попасть двумя способами:
    # 1) из i-2 командой "прибавить 2"
    # 2) из i//3 командой "умножить на 3", только если i делится на 3
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0)

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