Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У него есть две команды: A — вычти 1; B — найди целую часть от деления на 2. Программа для исполнителя — последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 8? Траектория вычислений — последовательность результатов выполнения всех команд программы.
Шешім по шагам
4 қадамОбозначим через $f(n)$ число программ, переводящих число $n$ в заданное конечное число. Последняя команда может быть A, тогда перед ней было $n-1$, или B, тогда перед ней было $\lfloor n/2\rfloor$.
$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$Для перехода из 30 в 8 вычисление рекуррентно даёт: $f(8)=1$, затем $f(9),\ldots,f(15)=1$, $f(16)=2$, и далее $f(30)=16$.
Для перехода из 8 в 1 получаем последовательность значений: $f(1)=1$, $f(2)=2$, $f(3)=3$, $f(4)=5$, $f(5)=7$, $f(6)=10$, $f(7)=13$, $f(8)=18$.
Так как все команды уменьшают число, после получения 8 вернуться к нему невозможно. Поэтому части программы можно выбирать независимо.
$$16\cdot18=288$$Где здесь ошибаются
Не учитывать, что число 8 должно появиться именно в траектории, то есть после выполнения команды.
Сложить числа способов вместо их перемножения.
Забыть, что команда B выполняет целочисленное деление на 2.