13. Анализ хода исполнения алгоритма: Сколько существует программ, для которых при исходном числе…
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычти $1$
2. Найди целую часть от деления на $2$
Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $32$ результатом является число $1$, и при этом траектория вычислений содержит число $9$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе $10$ траектория состоит из чисел $9$, $4$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $9$, разбивается на две части: $32\rightarrow9\rightarrow1$.
Посчитаем количество программ от $32$ до $9$ и от $9$ до $1$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 1, y) + f(x // 2, y)
print(f(32, 9) * f(9, 1))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$32\rightarrow9$: $16$,
$9\rightarrow1$: $23$.
$16\cdot23=368$.
Программа выведет: $368$.