Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами.
A. Вычесть 3
B. Поменять местами
Первая команда уменьшает число на экране на 3, вторая команда меняет разряды десятков и единиц в числе местами, причём она применяется только к числам, у которых цифра в разряде единиц меньше цифры в разряде десятков. Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 43 результатом является число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы AAB при исходном числе 26 траектория состоит из чисел 23, 20, 2.
Приведём решение на языке Python.
def change(x):
x1 = x // 10
x2 = x % 10
if x1 > x2:
return x2 * 10 + x1
else:
return x
def f(x, y):
if x < y :
return 0
if x == y:
return 1
else:
if x // 10 > x % 10:
return f(x - 3, y) + f(change(x), y)
else:
return f(x - 3, y)
print(f(43, 13))
Ответ: 4.