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

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

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 2, y) + f(x * 3, y)

print(f(2, 42))

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

a = [0] * 100
a[2] = 1
for i in range(3, 42 + 1):
    a[i] = a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
print(a[42])

Решение аналитикой:

Количество программ, которые преобразуют число 2 в число обозначим Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа:
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда Заполним таблицу по данной формуле:

Отсюда видим, что всего программ 15.