Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Поменяй местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 100 результатом является число 141?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.
Приведём решение на языке Python.
def change(x):
x = str(x)
if int(str(x)[2]) > int(str(x)[1]):
return int(x[0] + x[2] + x[1])
else:
return int(x)
def f(x, y):
if x > y :
return 0
if x == y:
return 1
else:
if int(str(x)[2]) > int(str(x)[1]) :
return f(x + 1, y) + f(change(x), y)
else:
return f(x + 1, y)
print(f(100, 141))
Ответ: 16.
Приведём решение Полины Егрушовой на языке Python.
def f(x,y):
if x > y:
return 0
if x==y:
return 1
else:
if int(str(x)[1]) < int(str(x)[2]):
return f(x+1,y)+f(int(str(x)[0]+str(x)[2]+str(x)[1]),y)
else:
return f(x+1,y)
print(f(100,141))