Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295609
Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить $1$
2. Прибавить $2$
3. Умножить на $2$
Первая из них увеличивает число на экране на $1$, вторая увеличивает его на $2$, третья умножает на $2$.
Программа для исполнителя К17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число $4$ в число $14$ и при этом траектория вычислений программы содержит числа $10$ и $12$? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе $7$ траектория будет состоять из чисел $8$, $16$, $18$.
Так как все команды только увеличивают число, траектория, содержащая числа $10$ и $12$, разбивается на три части: $4\rightarrow10\rightarrow12\rightarrow14$.
Посчитаем количество программ на каждом участке.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)
print(f(4, 10) * f(10, 12) * f(12, 14))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Количество путей:
$4\rightarrow10$: $16$,
$10\rightarrow12$: $2$,
$12\rightarrow14$: $2$.
$16\cdot2\cdot2=64$.
Программа выведет: $64$.
20
