Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 3; C — найти целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
Шешім по шагам
4 қадамТак как все команды уменьшают число, каждую программу можно рассматривать как путь от 19 к 3. Условие о наличии числа 12 позволяет разделить путь на участок от 19 до 12 и участок от 12 до 3.
Для каждого числа вычисляем количество способов попасть в него командами A, B и C. Переходы, приводящие в число 9, исключаем; переход C из числа n приводит в число $\lfloor n/2 \rfloor$.
Суммирование количества допустимых путей для всех возможных промежуточных чисел с обязательным прохождением через 12 даёт общее число программ.
После выполнения динамического подсчёта количество программ равно 153.
Где здесь ошибаются
Не учитывать, что число 12 должно входить в траекторию вычислений.
Разрешать переход в число 9.
Забывать, что команда C выполняет целочисленное деление на 2.
Считать только различные траектории, а не последовательности команд.