13. Анализ хода исполнения алгоритма: Первая из них увеличивает число на экране на 1, вторая…
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $3$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает его на $3$.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $2$ в число $14$ и при этом траектория вычислений программы содержит число $9$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $24$, $26$.
Так как все команды только увеличивают число, любая траектория, содержащая $9$, разбивается на две части:
$2\rightarrow9\rightarrow14$.
Посчитаем количество программ от $2$ до $9$ и от $9$ до $14$.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)
print(f(2, 9) * f(9, 14))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow9$: $25$,
$9\rightarrow14$: $8$.
$25\cdot8=200$.
Программа выведет: $200$.