Решение: Программы с заданной траекторией
Исполнитель преобразует число на экране. Команда A вычитает из числа 2, а команда B заменяет число на целую часть результата его деления на 2. Программа исполнителя является последовательностью команд. Сколько существует программ, которые при исходном числе 30 получают в результате число 1, причём траектория вычислений содержит число 14? Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Решение по шагам
3 шагаТак как обе команды уменьшают число, любую подходящую программу можно разделить в момент появления числа 14 на две независимые части: путь от 30 до 14 и путь от 14 до 1.
$$N(30 \to 1\text{ через }14)=N(30 \to 14)\cdot N(14 \to 1)$$Для каждого числа последовательно подсчитываем количество способов попасть из него в нужное целевое число. При этом учитываются переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.
Динамический подсчёт для двух участков даёт произведение количества вариантов, равное 36.
$$N(30 \to 14)\cdot N(14 \to 1)=36$$Где здесь ошибаются
Не учитывать условие обязательного прохождения через число 14.
Складывать количества программ вместо их перемножения.
Забывать, что команда B выполняет целочисленное деление на 2.