Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 4; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 9 и содержит 15? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Шешім по шагам
3 қадамИз каждого текущего числа рассматриваем три возможных перехода: вычитание 1, вычитание 4 и деление на 3 с взятием целой части. Переходы, после которых получается 9, не учитываем.
$$A(n)=n-1,\quad B(n)=n-4,\quad C(n)=\left\lfloor\frac{n}{3}\right\rfloor$$Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.
Последовательно заполняя значения для состояний, достижимых из 19, и суммируя только пути, заканчивающиеся в 2, получаем количество программ, траектория которых содержит 15 и не содержит 9.
Где здесь ошибаются
Не учитывать число 15, если оно является промежуточным результатом.
Отбрасывать программы только при исходном числе 9, хотя 9 может появиться позже в траектории.
Считать команды A, B и C одинаковыми при одинаковом результате.