13. Анализ хода исполнения алгоритма: Сколько существует программ, для которых при исходном числе…
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь $1$
B. Поменяй местами
Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $100$ результатом является число $150$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.
Так как обе команды увеличивают число, будем последовательно считать количество программ, переводящих число $100$ в число $150$.
Для команды B выделим цифры десятков и единиц. Если цифра десятков меньше цифры единиц, меняем их местами.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
k = f(x + 1, y)
a = x // 10 % 10
b = x % 10
if a < b:
z = x - 10 * a - b + 10 * b + a
k += f(z, y)
return k
print(f(100, 150))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена, и получаем новое число $z$ с переставленными цифрами.
Программа выведет: $35$.