Исполнитель Апельсин преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Программа для исполнителя Апельсин – это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является число 40?
Решение рекурсией:
# Модуль для того,
# чтобы функция не считала одни и те же значения по нескольку раз.
# Значительно ускоряет программу
from functools import lru_cache
@lru_cache(None)
def f(n, m):
if n == m:
return 1
if n > m:
return 0
return f(n+1, m) + f(n+2, m) + f(n*2, m)
print(f(5, 40))
Решение динамикой:
a = [0] * 100
a[5] = 1
for i in range(6, 41):
a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2== 0)
print(a[40])