Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Прибавить 3.
C. Умножить на 2.
Программа для исполнителя — это последовательность команд. Например, программа BAC при исходном
Сколько существует программ, которые преобразуют исходное
Приведём решение на языке Python.
def f(start, end, k):
if start > end + 1:
return 0
if start == end:
return 1
else:
if k == 1:
return f(start + 3, end, k - 1) + f(start * 2, end, k - 1)
else:
return f(start - 1, end, k + 1) + f(start + 3, end, k) + f(start * 2, end, k)
print(f(4, 14, 0))
Ответ: 46.
Приведём решение Полины Егрушовой на языке Python.
def f(x,y,s):
if x>y+1:
return 0
if x==y:
return 1
else:
if 'a' ==s[-1]:
return f(x+3,y,s+'b')+f(x*2,y,s+'c')
else:
return f(x+3,y,s+'b')+f(x*2,y,s+'c')+f(x-1,y,s+'a')
print(f(4,14,'//'))