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