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