Задание 23: Оператор присваивания и ветвления. Перебор вариантов, построение дерева

Типичная формулировка: "Исполнитель преобразует число на экране. У исполнителя есть команды с номерами 1, 2, 3... Программа — последовательность команд. Сколько существует программ, которые переводят число $A$ в число $B$, при этом траектория вычислений содержит (не содержит) число $C$?"

…

• Исполнитель — объект с фиксированным набором команд; каждая команда — функция, однозначно преобразующая число.
• Программа — конечная последовательность номеров команд, применяемых по порядку.
• Траектория вычислений — последовательность чисел, полученных после каждой команды (исходное число в неё не входит, конечное — входит).
• Принцип умножения: если путь состоит из двух независимых участков, реализуемых $n$ и $m$ способами, общее число программ равно $n \cdot m$.
• Рекуррентная формула количества программ, приводящих число $x_0$ к числу $x$ через набор команд с приростами $c_1, c_2, \dots, c_k$ (или деление для обратной операции умножения): $$N(x) = \sum_{i=1}^{k} N(x - c_i),$$ где $N(x_0) = 1$, а $N(x) = 0$, если значение $x$ недостижимо (меньше $x_0$ или не получается ни одной командой).
• Правило обязательного этапа: если траектория обязана содержать число $m$, то $$N_{\text{всего}} = N_{x_0 \to m} \cdot N_{m \to x_{\text{target}}}.$$
• Правило избегаемого этапа: чтобы запретить прохождение через $m$, при построении таблицы полагают $N(m) = 0$ независимо от того, что дала бы формула, — тогда все более дальние значения автоматически не учитывают пути через $m$.

1. Выписать все команды и числовые операции, которые они выполняют.
2. Определить исходное число $x_0$ и целевое $x_t$; убедиться, что команды монотонны (только увеличивают или только уменьшают число) — это гарантирует, что таблицу можно строить по возрастанию (или убыванию) без циклов.
3. Если есть обязательное число $m$: разбить задачу на две части — от $x_0$ до $m$ и от $m$ до $x_t$. Построить таблицу $N(x)$ для каждой части отдельно, начиная считать заново с единицы на старте своего участка.
4. Если есть избегаемое число $q$: строить единую таблицу от $x_0$ до $x_t$, но на каждом шаге, когда таблица "доходит" до значения $q$, принудительно поставить $N(q)=0$ и продолжать расчёт дальше как обычно. …