Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295612
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти $2$
B. Найди целую часть от деления на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $38$ результатом является число $2$, и при этом траектория вычислений содержит число $16$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе $13$ траектория состоит из чисел $11$, $5$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $16$, разбивается на две части: $38\rightarrow16\rightarrow2$.
Посчитаем количество программ от $38$ до $16$ и от $16$ до $2$.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 2, y) + f(x // 2, y)
print(f(38, 16) * f(16, 2))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$38\rightarrow16$: $3$,
$16\rightarrow2$: $12$.
$3\cdot12=36$.
Программа выведет: $36$.
20
