Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295613
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Умножить на $3$
2. Прибавить $2$
3. Прибавить $3$
Первая из них умножает число на экране на $3$, вторая увеличивает его на $2$, третья увеличивает его на $3$.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $2$ в число $21$ и при этом траектория вычислений программы содержит число $12$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе $7$ траектория будет состоять из чисел $21$, $23$, $26$.
Так как все команды только увеличивают число, любая траектория, содержащая $12$, разбивается на две части: $2\rightarrow12\rightarrow21$.
Посчитаем количество программ от $2$ до $12$ и от $12$ до $21$.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x * 3, y) + f(x + 2, y) + f(x + 3, y)
print(f(2, 12) * f(12, 21))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$2\rightarrow12$: $10$,
$12\rightarrow21$: $5$.
$10\cdot5=50$.
Программа выведет: $50$.
20
