Исполнитель ТриЧетыреПять преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 3
2. Прибавить 4
3. Умножить на 5
Программа для исполнителя ТриЧетыреПять – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 100, и при этом траектория вычислений содержит число 50?
Рекурсия:
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 3, y) + f(x + 4, y) + f(x * 5, y)
print(f(2, 50) * f(50, 100))
Динамика:
a = [0] * 101
a[2] = 1
for i in range(3, 101):
a[i] = a[i - 3] + a[i - 4] + a[i // 5] * (i % 5 == 0)
if i == 50:
for j in range(i):
a[j] = 0
print(a[100])