Исполнитель преобразует число на экране.
У исполнителя есть четыре команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
4. Умножить на 3.
Первая команда увеличивает число на экране
Программа для исполнителя — это последовательность команд. Например, если в начальный момент на экране находится
Сколько существует программ, которые преобразуют исходное
Приведём решение на языке Python.
def f(start, end, fl1, fl2):
if start == end:
return 1
if start > end:
return 0
if start < end:
if fl1 == False:
return f(start * 2, end, True, False) + f(start * 3, end, True, False)
if fl2 == False:
return f(start + 1, end, False, True) + f(start + 2, end, False, True)
else:
return f(start + 1, end, False, True) + f(start + 2, end, False, True) + f(start * 2, end, True, False) + f(start * 3, end, True, False)
print(f(1, 24, True, True))
Таким образом, количество программ, удовлетворяющих условию задачи и выведенное на экран,
Ответ: 9.
Приведём решение Альберт К. на языке Python.
def F(x, y, oper):
if x==y:
return 1
if x > y:
return 0
if oper == 0:
return F(x*2, y, 1) + F(x*3, y, 1)
else:
return F(x+1, y, 0) + F(x+2, y, 0)
print(F(1, 24, 0) + F(1, 24, 1))
Приведём решение Юрия Красильникова на языке Python.
def f(s,e,p):
if s > e: return 0
if s == e: return 1
r = 0
if p != 'У':
r += f(s*2,e,'У') + f(s*3,e,'У')
if p != 'П':
r += f(s+1,e,'П') + f(s+2,e,'П')
return r
print(f(1,24,'А'))
# т.к. 'А' не равно ни 'У', ни 'П', то при первом вызове используется и сложение, и умножение