13. Анализ хода исполнения алгоритма: Сколько существует программ, которые преобразуют исходное…
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить $1$
B. Прибавить $2$
C. Умножить на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число $4$ в число $15$, и при этом траектория вычислений программы содержит числа $11$ и $13$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $18$.
Так как все команды только увеличивают число, траектория, содержащая числа $11$ и $13$, разбивается на три части: $4\rightarrow11\rightarrow13\rightarrow15$.
Посчитаем количество программ на каждом участке.
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 * 2, y)
print(f(4, 11) * f(11, 13) * f(13, 15))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$4\rightarrow11$: $25$,
$11\rightarrow13$: $2$,
$13\rightarrow15$: $2$.
$25\cdot2\cdot2=100$.
Программа выведет: $100$.