У исполнителя Кабачок есть три команды, которым присвоены номера:
1. Прибавить 2
2. Прибавить 4
3. Прибавить 5
Определите число, для получения которого из числа 31 существует 1001 программа.
Решение 1 (Рекурсия):
def f(x, y):
if x > y:
return 0
if x == y:
return 1
return f(x + 2, y) + f(x + 4, y) + f(x + 5, y)
for y in range(32, 70):
if f(31, y) == 1001:
print(y)
Решение 2 (Динамика):
a = [0] * 100
a[31] = 1
for i in range(32, 100 + 1):
a[i] = a[i-2] + a[i-4] + a[i-5]
if a[i] == 1001:
print(i)
break
Ответ: 56