У исполнителя Прибавитель две команды, которым присвоены номера:
1. прибавь 1,
2. увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Программа для Прибавителя — это последовательность команд. Сколько есть программ, которые число 25 преобразуют в число 47?
Обе команды увеличивают исходное число. Старшая цифра — 2, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 25 число 35, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 47. Таким образом, получаем программы: 211...1, 121...1, и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует всего одна программа, в которой команда 2 не используется: 111....1.
Таким образом, имеем 6 + 13 + 1 = 20 программ.
Ответ: 20.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
else:
return f(x + 1, y) + f(x + 10, y)
print(f(25, 47))