Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295606
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть $1$
B. Вычесть $3$
C. Найти целую часть от деления на $2$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $19$ результатом является число $3$, при этом траектория вычислений не содержит числа $9$ и содержит $12$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $13$ траектория состоит из чисел $6$, $3$, $2$.
Так как все команды только уменьшают число, любая траектория, содержащая $12$, разбивается на две части: $19\rightarrow12\rightarrow3$.
Посчитаем количество программ от $19$ до $12$ и от $12$ до $3$. Число $9$ запрещаем.
def f(x, y):
if x == y:
return 1
if x < y or x == 9:
return 0
return f(x - 1, y) + f(x - 3, y) + f(x // 2, y)
print(f(19, 12) * f(12, 3))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $9$, такая траектория не подходит.
Количество путей:
$19\rightarrow12$: $9$,
$12\rightarrow3$: $17$.
$9\cdot17=153$.
Программа выведет: $153$.
20
