Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Увеличь на 1
2. Увеличь на 3
3. Умножь на 4
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 824, при этом траектория вычислений содержит числa 21 и 68, причём можно использовать только ту команду, чей номер отличается на 1 от номера команды, выполненной на предыдущем шаге?
Программное решение:
# c — номер команды на предыдущем шаге
# r1 — флаг наличия в траектории 21
# r2 — флаг наличия в траектории 68
def f(a, b, c = 0, r1 = False, r2 = False):
if a > b:
return 0
if a == b and r1 and r2:
return 1
if a == 21:
r1 = True
if a == 68:
r2 = True
if c == 1 or c == 3:
return f(a + 3, b, 2, r1, r2)
if c == 2:
return f(a + 1, b, 1, r1, r2) + f(a * 4, b, 3, r1, r2)
return f(a + 1, b, 1, r1, r2) + f(a + 3, b, 2, r1, r2) + f(a * 4, b, 3, r1, r2)
print(f(1, 824))
Ответ: 36