Исполнитель Укроп преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.
Программа для исполнителя Укропа — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 24 и при этом траектория вычислений содержит число 14?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.
Рекурсия:
def f(a,b):
if a > b:
return 0
if a == b:
return 1
if a < b:
return f(a + 1, b) + f(a * 2, b) + f(a + 3, b)
print(f(2, 14) * f(14, 24))
Динамика:
a = [0] * 25
a[2] = 1
for i in range(3, 25):
a[i] = a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0)
if i == 14:
for j in range(i):
a[j] = 0
print(a[24])