Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295611
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить $1$
2. Умножить на $2$
Первая команда увеличивает число на экране на $1$, вторая умножает его на $2$.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $2$ результатом является число $29$ и при этом траектория вычислений содержит число $14$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $17$.
Так как все команды только увеличивают число, любая траектория, содержащая $14$, разбивается на две части: $2\rightarrow14\rightarrow29$.
Посчитаем количество программ от $2$ до $14$ и от $14$ до $29$.
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(2, 14) * f(14, 29))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow14$: $13$,
$14\rightarrow29$: $2$.
$13\cdot2=26$.
Программа выведет: $26$.
20
