Шешімі: Подсчёт траекторий исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — вычти 2; B — найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 38 результатом является число 2, и при этом траектория вычислений содержит число 16? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Шешім по шагам
4 қадамРассмотрим сначала программы, переводящие число 38 в число 16. Обозначим через $f(n)$ количество способов попасть из $n$ в 16. Для каждого числа учитываем переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.
$$f(n)=f(n-2)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$$Последовательное вычисление значений от 16 до 38 даёт: $f(18)=1$, $f(20)=1$, $f(22)=1$, $f(24)=1$, $f(26)=1$, $f(28)=1$, $f(30)=1$, $f(32)=2$, $f(34)=2$, $f(36)=3$, $f(38)=3$. Значит, из 38 в 16 можно попасть 3 способами.
Теперь обозначим через $g(n)$ количество способов попасть из $n$ в 2. По той же рекуррентной формуле получаем $g(2)=1$, $g(4)=2$, $g(6)=2$, $g(8)=4$, $g(10)=5$, $g(12)=7$, $g(14)=8$, $g(16)=12$.
Любая программа, проходящая через 16, составляется из программы перехода 38 в 16 и программы перехода 16 в 2. Поэтому количества способов перемножаются.
$$3\cdot 12=36$$Где здесь ошибаются
Складывают, а не перемножают количество путей до 16 и после 16.
Не учитывают обе команды при построении рекуррентной формулы.
Считают программы, которые достигают числа 2, но не проходят через 16.