Исполнитель Крабик преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавить
; - Умножить на
.
Программа для исполнителя Крабика — это последовательность команд. Сколько существует программ, которые число 
преобразуют в число 
?
Решение рекурсией:
def f(x, y):
if x > y:
return 0
if x == y:
return 1
return f(x + 1, y) + f(x * 4, y)
print(f(1, 55))
Решение динамикой 1:
a = [0] * 56
a[1] = 1
for i in range(2, 56):
a[i] = a[i - 1] + a[i // 4] * (i % 4 == 0)
print(a[55])
Решение рекурсией 2:
a = [0] * 500
a[1] = 1
for i in range(1, 55):
a[i + 1] += a[i]
a[i * 4] += a[i]
print(a[55])