Задание 23 ЕГЭ по информатике: подсчёт программ исполнителя с условиями

Что проверяет задание

Задание 23 проверяет умение работать с формальным исполнителем: набором пронумерованных команд, каждая из которых меняет число на экране по строгому правилу (прибавить, умножить, разделить и т.п.). Нужно посчитать, сколько существует программ — последовательностей команд, — которые переводят одно число в другое, причём траектория вычислений (все промежуточные результаты) обязана либо содержать, либо не содержать определённое число.

Задание проверяет не столько знание программирования, сколько умение выстроить рекуррентный подсчёт вариантов без полного перебора: понимание принципа умножения комбинаторики, работу с динамическим программированием "на бумаге" и аккуратность в построении таблиц количества путей.

Как выглядит формулировка и сколько баллов

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

Задание находится в части с кратким ответом, требует записать одно целое число — количество программ. Оценивается в 2 балла. Отдельного текста программы или кода писать не нужно — задача решается вычислениями и логикой на черновике. Сложность обычно средняя-высокая, так как требует точного построения таблицы значений без ошибок в диапазонах.

Что нужно знать

• Исполнитель — объект с фиксированным набором команд; каждая команда — функция, однозначно преобразующая число.
• Программа — конечная последовательность номеров команд, применяемых по порядку.
• Траектория вычислений — последовательность чисел, полученных после каждой команды (исходное число в неё не входит, конечное — входит).
• Принцип умножения: если путь состоит из двух независимых участков, реализуемых $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. Метод таблицы количества путей (динамическое программирование). Строится таблица $N(x)$ от начального числа до целевого, каждое значение — сумма количества путей во "предыдущие" числа по всем командам. Мини-пример: команды +1 и +2, старт 1, цель 4. $N(1)=1$, $N(2)=N(1)=1$, $N(3)=N(2)+N(1)=2$, $N(4)=N(3)+N(2)=3$. Ответ: 3 программы.

2. Метод обязательного промежуточного значения. Траекторию разбивают на два участка: от старта до обязательного числа $m$ и от $m$ до цели, считают отдельные таблицы и умножают результаты. Мини-пример: те же команды, старт 1, цель 4, обязательно число 3. Путей 1→3: 2 (посчитано выше). Путей 3→4: только +1, то есть 1 путь. Итог: $2 \cdot 1 = 2$.

3. Метод запрета (избегаемый этап). В таблице значение запрещённого числа искусственно приравнивают к нулю, даже если оно естественно достижимо. Мини-пример: команды +1, +2, старт 1, цель 4, избегаем число 2. $N(1)=1$, $N(2)=0$ (запрет), $N(3)=N(2)+N(1)=0+1=1$, $N(4)=N(3)+N(2)=1+0=1$. Ответ: 1 программа.

4. Комбинированный метод (обязательный плюс избегаемый этап). Траекторию делят по обязательным точкам на участки, и в каждом участке отдельно проверяют, попадает ли туда запрещённое число; если да — применяют запрет именно в этом участке. Мини-пример: команды +1, +2, старт 1, цель 5, обязательно число 3, избегаем число 2. Участок 1→3 с запретом 2: $N(1)=1,N(2)=0,N(3)=N(2)+N(1)=1$. Участок 3→5 (запрет 2 уже не влияет, так как 2<3): $M(3)=1,M(4)=M(3)+M(2\text{ невозможно})=1,M(5)=M(4)+M(3)=2$. Итог: $1 \cdot 2 = 2$.

5. Метод дерева перебора. Применяется при очень коротких программах (2–4 команды) как способ проверки: строится дерево всех вариантов вручную, ветви отбрасываются, если не выполняется условие. Удобен для контроля правильности таблицы, но неэффективен при длинных программах.

Алгоритм решения по шагам

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$ и продолжать расчёт дальше как обычно.
5. Если условия сочетаются (обязательное и избегаемое): сначала разбить по обязательным точкам, затем в каждом участке проверить, входит ли туда запрещённое число, и применить запрет только там, где нужно.
6. Перемножить или сложить полученные значения по правилу, соответствующему структуре задачи (независимые последовательные участки — умножение).
7. Проверить результат на разумность: он должен быть целым положительным числом, и порядок величины должен соответствовать длине программы и количеству команд (слишком большие или нулевые ответы — сигнал перепроверить таблицу).

Разбор примеров

Пример 1. Команды: 1) +1, 2) +2, 3) умножить на 2. Исходное число 3, результат 12, траектория обязательно содержит 10.

Шаг 1. Считаем $N(x)$ — количество программ от 3 до $x$, используя обратные переходы: $x-1$, $x-2$, а также $x/2$, если $x$ чётное.

$N(3)=1$; $N(4)=N(3)=1$; $N(5)=N(4)+N(3)=2$; $N(6)=N(5)+N(4)+N(3)=4$ (учли деление $6/2=3$); $N(7)=N(6)+N(5)=6$; $N(8)=N(7)+N(6)+N(4)=11$; $N(9)=N(8)+N(7)=17$; $N(10)=N(9)+N(8)+N(5)=17+11+2=30$.

Шаг 2. Считаем $M(x)$ — количество программ от 10 (обязательного числа) до 12: $M(10)=1$; $M(11)=M(10)=1$; $M(12)=M(11)+M(10)=2$ (деление $12/2=6$ невозможно, так как $6<10$).

Шаг 3. Умножаем: $30 \cdot 2 = 60$. Ответ совпадает с эталонным: 60.

Пример 2. Команды: 1) +1, 2) +3. Исходное число 1, результат 17, траектория обязательно содержит 9.

Шаг 1. Считаем $N(x)$ от 1 до 9: $N(1)=1$, $N(2)=1$, $N(3)=1$, $N(4)=N(3)+N(1)=2$, $N(5)=N(4)+N(2)=3$, $N(6)=N(5)+N(3)=4$, $N(7)=N(6)+N(4)=6$, $N(8)=N(7)+N(5)=9$, $N(9)=N(8)+N(6)=13$.

Шаг 2. Считаем $M(x)$ от 9 до 17: $M(9)=1$, $M(10)=1$, $M(11)=1$, $M(12)=M(11)+M(9)=2$, $M(13)=M(12)+M(10)=3$, $M(14)=M(13)+M(11)=4$, $M(15)=M(14)+M(12)=6$, $M(16)=M(15)+M(13)=9$, $M(17)=M(16)+M(14)=13$.

Шаг 3. Умножаем: $13 \cdot 13 = 169$. Совпадает с эталонным ответом.

Пример 3. Команды: 1) +1, 2) +2, 3) +4. Исходное число 1, результат 15, траектория обязательно содержит 8.

Шаг 1. Считаем $N(x)$ от 1 до 8: $N(1)=1$, $N(2)=1$, $N(3)=N(2)+N(1)=2$, $N(4)=N(3)+N(2)=3$, $N(5)=N(4)+N(3)+N(1)=6$, $N(6)=N(5)+N(4)+N(2)=10$, $N(7)=N(6)+N(5)+N(3)=18$, $N(8)=N(7)+N(6)+N(4)=31$.

Шаг 2. Считаем $M(x)$ от 8 до 15: $M(8)=1$, $M(9)=1$, $M(10)=M(9)+M(8)=2$, $M(11)=M(10)+M(9)=3$, $M(12)=M(11)+M(10)+M(8)=6$, $M(13)=M(12)+M(11)+M(9)=10$, $M(14)=M(13)+M(12)+M(10)=18$, $M(15)=M(14)+M(13)+M(11)=31$.

Шаг 3. Умножаем: $31 \cdot 31 = 961$. Совпадает с эталонным ответом.

Все три примера показывают одну и ту же логику: разбить путь на два участка через обязательную точку, построить для каждого свою таблицу с единицей на старте участка и нулями для недостижимых значений, затем перемножить итоговые числа.

Типичные ошибки и ловушки

• Забывают, что исходное число не входит в траекторию, а конечное — входит; это меняет, какие значения нужно "закрывать" запретом.
• При обязательном этапе начинают вторую таблицу не с единицы на самом числе $m$, а продолжают первую таблицу — это даёт неверный результат, так как вторая часть пути должна считаться как отдельная задача с новым стартом.
• При работе с командой умножения/деления забывают проверить, что частное целое и не меньше стартового значения — иначе в таблицу попадают несуществующие переходы.
• При избегаемом этапе вычитают количество "плохих" путей из общего числа вместо того, чтобы просто обнулить значение в таблице на нужном шаге — это приводит к двойному учёту или потере части путей.
• В комбинированных задачах забывают проверить, попадает ли запрещённое число в каждый из участков между обязательными точками, и применяют запрет во всех участках сразу или ни в одном.
• Путают понятие "траектория содержит число" с "число получено на конкретном шаге" — важно, что число могло появиться на любом шаге, а не строго на определённом месте программы.
• Допускают арифметические ошибки при последовательном сложении в таблице — рекомендуется проверять промежуточные суммы хотя бы раз повторным подсчётом.

Как готовиться

• Тренироваться строить таблицы количества путей вручную для разных наборов команд: только сложение, сложение и умножение, сложение и вычитание.
• Разобрать отдельно случаи с обязательным этапом, с избегаемым этапом и с их сочетанием — на 3–5 задачах каждого типа, чтобы автоматизировать разбиение на участки.
• Для команд умножения/деления обязательно проверять на каждом шаге целочисленность и допустимый диапазон обратного перехода.
• Для коротких программ (до 3–4 шагов) периодически проверять результат построением дерева вариантов — это помогает находить ошибки в таблице.
• Замечать закономерность: если команды — только +1 и +k, количество путей от $a$ до $b$ подчиняется рекуррентности, похожей на числа Фибоначчи или на подсчёт способов замостить отрезок плитками длины 1 и $k$; узнавание такого шаблона ускоряет решение.
• Отрабатывать скорость: цель — решать подобные задачи за 5–7 минут, используя таблицу, а не полный перебор.
• После решения всегда делать быструю проверку правдоподобия ответа: сравнить порядок величины с количеством возможных программ данной длины, чтобы отсеять грубые арифметические ошибки.