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

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

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (умножить на 3, умножить на 2, число во второй степени), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

def f(st, fn):
    if st == fn: # Если дошли до нужного числа
        return 1
    if st > fn: # Если число стало больше нужного
        return 0
    a = [0] * (st * st) # Массив с количеством путей до нашего числа
    for i in range(2, st + 1):
        a[i] = f(st * i, fn) # Заполняем массив по условию задачи
    return sum(a) # Количество путей до нашего числа
print(f(2, 60)) # Найдем ответ по условию задачи

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i // 2, i ** 0.5 (корень из числа) и i // 4.

# Создаем массив для хранения количества путей до чисел от 2 до 59
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 60 * 60
a[2] = 1 # Начальное число
# Перебираем числа в нужном диапазоне
for i in range(2, 60):
    for j in range(2, i + 1): # Найдем количество путей до каждого числа по условию задачи
        a[i * j] += a[i]
print(a[60]) # Найдем ответ по условию задачи