Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами.
A. Прибавь 1
B. Умножь на 2
C. Умножь на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, которые преобразуют число 6 в число 48, и при этом траектория вычислений содержит 14 или 18? Траектория должна содержать хотя бы одно из указанных чисел.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 3 траектория состоит из чисел 4, 12, 24.
Приведём решение на языке Python.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)
print(f(6, 14) * f(14, 48) + f(6, 18) * f(18, 48) - f(6,14)*f(14,18)*f(18,48))
Ответ: 69.
Приведём решение Маргариты Фалько на языке Python.
def f (a, b, n):
if a > b:
return 0
if a == b and n > 0:
return 1
if a == 14 or a == 18:
return f(a+1, b, n+1) + f(a*2, b, n+1) + f(a*3, b, n+1)
return f(a+1, b, n) + f(a*2, b, n) + f(a*3, b, n)
print(f(6, 48, 0))