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