Исполнитель преобразует число на экране. У исполнителя есть четыре команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
4. Умножить на 3.
Первая команда увеличивает число на экране
Программа для исполнителя — это последовательность команд. Например, если в начальный момент на экране находится
Сколько существует программ, которые преобразуют исходное
Приведём решение на языке Python.
def f(start, end, k):
if start > end:
return 0
if start == end and k == 1:
return 1
else:
return f(start + 1, end, k) + f(start + 2, end, k) + f(start * 2, end, k + 1) + f(start * 3, end, k + 1)
print(f(1, 10, 0))
Здесь k — счетчик, который отвечает за то, сколько раз было использовано умножение.
Ответ: 96.
Приведём решение Юрия Красильникова на языке Python.
def f(s,e,t):
if s > e: return 0
if s == e: return 1 if t.count('3')+t.count('4') == 1 else 0
return f(s+1,e,t+'1') + f(s+2,e,t+'2') + f(s*2,e,t+'3') + f(s*3,e,t+'4')
print(f(1,10,''))