Решение: Траектория вычислений исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — вычти 1; B — найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 32 результатом является число 1 и при этом траектория вычислений содержит число 10? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Решение по шагам
5 шаговОбозначим через $f(n)$ количество программ, переводящих число $n$ в число 1. Для $n>1$ последняя команда может быть A или B, поэтому используем рекуррентный подсчёт.
$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$Последовательно вычисляя значения, получаем:
$$f(1),\ldots,f(10)=1,2,3,5,7,10,13,18,23,30$$Следовательно, количество программ, переводящих 10 в 1, равно $30$.
Теперь считаем количество путей из 32 в 10. Пусть $g(n)$ — число путей из $n$ в 10, причём $g(10)=1$. Для чисел больше 10:
$$g(n)=g(n-1)+g(\lfloor n/2\rfloor),\quad g(k)=0\text{ при }k<10$$Вычисления от 10 до 32 дают $g(32)=14$. Каждая программа, проходящая через 10, однозначно состоит из пути от 32 до 10 и пути от 10 до 1.
$$14\cdot30=420$$Где здесь ошибаются
Не учитывать, что траектория должна содержать число 10.
Сложить вместо умножения количество путей до 10 и после 10.
Забыть, что команда B выполняет целочисленное деление на 2.