13. Анализ хода исполнения алгоритма: Прибавить 2, Прибавить 3, Умножить на 2
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить $2$
B. Прибавить $3$
C. Умножить на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $3$ результатом является число $25$, при этом траектория вычислений содержит число $10$ и не содержит $17$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $7$ траектория будет состоять из чисел $14$, $17$, $19$.
Так как все команды только увеличивают число, любая траектория, содержащая $10$, разбивается на две части:
$3\rightarrow10\rightarrow25$.
Посчитаем количество программ от $3$ до $10$ и от $10$ до $25$. Число $17$ запрещаем.
def f(x, y):
if x == y:
return 1
if x > y or x == 17:
return 0
return f(x + 2, y) + f(x + 3, y) + f(x * 2, y)
print(f(3, 10) * f(10, 25))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $17$, такая траектория не подходит.
Количество путей:
$3\rightarrow10$: $5$,
$10\rightarrow25$: $18$.
$5\cdot18=90$.
Программа выведет: $90$.