Шешімі: Подсчёт программ с числом 11
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1) «Вычти 1» — уменьшает число на экране на 1; 2) «Найди целую часть от деления на 2» — заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 32 результатом является число 1, и при этом траектория вычислений содержит число 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Шешім по шагам
4 қадамОбозначим через $f(n)$ количество программ, переводящих число n в число 1. Для числа 1 имеем $f(1)=1$. Для остальных чисел последняя команда перед переходом из n может быть применена после получения числа $n-1$ или числа $\lfloor n/2 \rfloor$, поэтому
$$f(n)=f(n-1)+f(\lfloor n/2 \rfloor)$$Последовательно вычисляя значения от 1 до 11, получаем $f(11)=37$.
Теперь обозначим через $g(n)$ количество программ, переводящих число n в число 11. Для $n<11$ имеем $g(n)=0$, а $g(11)=1$. По той же рекуррентной формуле получаем: $g(22)=2$, $g(23)=3$, $g(24)=4$, ..., $g(32)=12$.
Любая программа, траектория которой содержит 11, однозначно распадается на часть от 32 до 11 и часть от 11 до 1. Поэтому количества способов перемножаются.
$$12 \cdot 37=444$$Где здесь ошибаются
Складывают, а не перемножают количество программ до 11 и после 11.
Не учитывают оба возможных перехода: вычитание 1 и деление на 2 с взятием целой части.
Считают только один способ достижения числа 11.