Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране
Программа для исполнителя — это последовательность команд. Например, если в начальный момент на экране находится
Сколько существует программ, которые преобразуют исходное
Приведём решение на языке Python.
def f(start, end, k, c):
if start > end:
return 0
if start == end:
return 1
if start < end:
if k == c == '+':
return f(start*2, end, '*', k)
elif k == c == '*':
return f(start + 1, end, '+', k)
else:
return f(start + 1, end, '+', k) + f(start * 2, end, '*',k)
print(f(1, 16, '0', '0'))
Здесь k и с — переменные, которые отвечают за то, чтобы не повторялись умножение и сложение более двух раз подряд.
Ответ: 5.
Приведём решение Ксении Ельцовой на языке Python.
def f (start, end, s):
if start == end and '+++' not in s and '***' not in s:
return 1
elif start > end:
return 0
return f(start + 1, end, s + '+')+ f(start*2, end, s + '*')
print(f(1, 16, ''))