Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: вычесть 1 и найти целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Решение по шагам
4 шагаРассмотрим количество программ, переводящих число $n$ в число 12. Для последнего действия перед достижением результата $n$ возможны переходы из $n-1$ командой A и из $\lfloor n/2\rfloor$ командой B.
$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$При вычислении от 12 до 30 получаем: $f(30)=8$. Это количество программ, которые переводят 30 в 12.
Теперь аналогично считаем количество программ, переводящих 12 в 1. При $g(1)=1$ и $g(n)=g(n-1)+g(\lfloor n/2\rfloor)$ получаем $g(12)=47$.
Любая подходящая программа состоит из участка от 30 до 12 и участка от 12 до 1. Поэтому количества программ перемножаются.
$$8\cdot47=376$$Где здесь ошибаются
Считать только программы от 30 до 12 или только программы от 12 до 1.
Не учитывать оба возможных перехода: вычитание 1 и деление на 2.
Складывать, а не перемножать количества программ до и после достижения числа 12.