Исполнитель преобразует число на экране.
У исполнителя есть четыре команды, которым присвоены номера.
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, 22, True, True))
Таким образом, количество программ, удовлетворяющих условию задачи и выведенное на экран,
Ответ: 11.
Приведём решение Ксении Ельцовой на языке Python.
def f(x,y,s):
if x == y and not "++" in s and not "**" in s:
return 1
if x > y:
return 0
return f(x+1,y,s+'+') + f(x+2,y,s+'+') + f(x*2,y,s+'*') + f(x*3,y,s+'*')
print(f(1,22,''))
Приведём решение Михаила Глинского на языке Python.
def f(a,b,c):
if a==b:
return 1
if a>b:
return 0
else:
if c=='c':
return f(a*2,b,'u')+f(a*3,b,'u')
if c=='u':
return f(a+1,b,'c')+f(a+2,b,'c')
else:
return f(a*2,b,'u')+f(a*3,b,'u')+f(a+1,b,'c')+f(a+2,b,'c')
print(f(1,22,'n'))