Исполнитель КотПесДруг преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Прибавить 6
3. Умножить на 3
Программа для исполнителя КотПесДруг – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 42, и при этом траектория вычислений содержит число 14 и не содержит число 20?
Рекурсия:
def f(n, m):
if n == m:
return 1
if n > m or n == 20:
return 0
return f(n + 2, m) + f(n + 6, m) + f(n * 3, m)
# Сначала доходим до 14, потом из 14 до 42, перемножаем траектории
print(f(4, 14) * f(14, 42))
Динамика:
a = [0] * 43
a[4] = 1
for i in range(5, 43):
a[i] = a[i - 2] + a[i - 6] + a[i // 3] * (i % 3 == 0)
if i == 14:
for j in range(i):
a[j] = 0
if i == 20:
a[i] = 0
print(a[42])