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