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

Q: Что проверяет задание 13 ЕГЭ по информатике?

Умение анализировать ход исполнения алгоритма для исполнителя-Вычислителя с несколькими простыми командами (например «прибавь 1», «умножь на 2»). Нужно посчитать, сколько существует программ, переводящих число A в число B, при условии, что траектория вычислений содержит или не содержит заданные числа. В кодификаторе это элемент содержания 3.3, код проверяемого требования 2.11, раздел «Алгоритмы и программирование».

Q: Сколько баллов даёт задание 13 и сколько времени на него отводится?

1 первичный балл по принципу «всё или ничего»: ответ либо полностью совпадает с эталоном, либо задание оценивается в 0. По обобщённому плану ФИПИ на задание 13 отводится примерно 7 минут. Уровень сложности — повышенный. Файла к заданию не прилагается, специализированное программное обеспечение не требуется.

Q: Как решать задание 13: какой метод самый надёжный?

Динамическое программирование по числам. Вводится величина K(n) — количество программ, переводящих число n в заданное конечное число. База: K(конечного числа) = 1. Переход: K(n) равно сумме K по всем состояниям, куда можно попасть из n одной командой. Считать нужно в направлении от конечного числа к начальному (или наоборот — в зависимости от того, увеличивают или уменьшают число команды исполнителя).

Q: Как учитывать обязательное промежуточное число в траектории?

Разбить задачу на независимые участки по этому числу и перемножить количества программ для каждого участка. Например, если траектория из A в B обязана пройти через M, ответ равен произведению количества программ из A в M на количество программ из M в B — это правило произведения, а не суммы: любой первый кусок можно свободно сочетать с любым вторым.

Q: А как учитывать запрещённое число в траектории?

Достаточно объявить, что количество программ через запрещённое число равно нулю (K(запрещённого) = 0), и вести подсчёт как обычно. Если запрет и обязательное число заданы одновременно, сначала разрезают задачу по обязательному числу на участки, а затем в каждом участке, где запрещённое число теоретически достижимо, отдельно обнуляют его K.

Q: Почему нельзя просто скопировать код из одного задания 13 в другое?

Потому что условие обрыва рекурсии зависит от направления команд. Если все команды увеличивают число, обрыв — при n больше конечного числа. Если все команды уменьшают число, обрыв — при n меньше конечного числа. Спутав направления, можно получить бесконечную рекурсию или тихо неверный (заниженный) ответ без явной ошибки выполнения.

Q: Нужно ли учитывать порядок команд в программе?

Да, но не напрямую: метод K(n) уже учитывает порядок автоматически, потому что каждая программа однозначно соответствует одной последовательности переходов между числами. Разные последовательности команд, ведущие к одинаковым промежуточным числам, считаются как разные программы и суммируются как отдельные слагаемые в формуле K(n).

Q: Как записать ответ на задание 13 в бланке?

Ответ — одно число, количество программ. Никаких слов «программ», единиц измерения и самих букв команд в ответе быть не должно — только число без пробелов и разделителей. Ответы в открытом банке нередко бывают трёх- и четырёхзначными, это нормально для задания такого типа.

Задание 13 ЕГЭ по информатике (КЕГЭ) — это исполнитель-Вычислитель с несколькими простыми командами (например «прибавь 1», «прибавь 2», «умножь на 2») и вопрос: сколько существует программ, переводящих число $A$ в число $B$ , при условии, что траектория вычислений обязана содержать (или, наоборот, не должна содержать) заданные числа. По кодификатору это код требования 2.11, элемент содержания 3.3 — то есть ФИПИ прямо называет это «умением анализировать ход исполнения алгоритма». Задание повышенного уровня сложности, за него дают 1 первичный балл. В 2027 году эта тема переехала с позиции 23 на позицию 13, а примерное время выполнения сократилось с 8 до 7 минут. Файла к заданию не прилагается, специализированное программное обеспечение не требуется, а ответ — одно число. Решается задание одним универсальным приёмом — динамическим программированием по числам: вы считаете, сколькими способами можно дойти до каждого промежуточного числа, а обязательные и запрещённые точки маршрута превращают задачу в произведение независимых участков. В статье — вся теория метода, рабочий код на Python (и цикл, и рекурсия с кэшированием) и три разбора реальных заданий из открытого банка ФИПИ с проверенными ответами. Потренироваться можно на реальных заданиях 13 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.

Что проверяет задание 13 ЕГЭ по информатике

Раздел кодификатора — «Алгоритмы и программирование», элемент содержания 3.3 («Умение исполнить алгоритм для формального исполнителя с заданной системой команд»), код проверяемого требования — 2.11. Формулировка умения из обобщённого плана варианта КИМ звучит так: «умение анализировать ход исполнения алгоритма». В отличие от задания 5 или 6 (тот же раздел, но базовый уровень и короткая цепочка команд, которую можно пройти вручную), здесь вручную перебрать все программы нереально: их количество растёт экспоненциально с числом шагов, а сама траектория подчинена ещё и дополнительному условию про обязательное или запрещённое число.

Проверяемые умения (КЭС 3.3, код требования 2.11)

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

Параметр	Значение
Максимальный балл	1 первичный (частичного зачёта нет: ответ либо полностью совпал с эталоном, либо 0)
Уровень сложности	Повышенный (П) — одно из 11 заданий этого уровня в работе
Формат ответа	Краткий: одно число (количество программ)
Раздел кодификатора	3. Алгоритмы и программирование; КЭС 3.3; код требования 2.11
Нужен ли файл / спец. ПО	Нет — условие даёт список команд исполнителя и оба числа прямо в тексте
Примерное время выполнения	7 минут (Обобщённый план варианта КИМ, СПЕЦ ЕГЭ-2027 по информатике)
Связанные задания	Задание 5 и задание 6 (тот же раздел КЭС 3.3, но базовый уровень и короткая программа), задание 12 (КЭС 3.3, тоже повышенный уровень, но исполнитель работает со строками, а не с числами)

Тренируйтесь на реальных заданиях

Задания 13 ЕГЭ по информатике из открытого банка ФИПИ с мгновенной проверкой ответа. Решаем, ошибаемся, разбираем — бесплатно.

Решать задание 13

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

Условие задания 13 почти всегда начинается с одного и того же определяющего блока — он не меняется от варианта к варианту и задаёт всю терминологию исполнителя:

Дальше идёт сам вопрос. У него есть три устойчивых подтипа — отличаются они условием на траекторию:

«Сколько существует программ, которые преобразуют исходное число 4 в число 15, и при этом траектория вычислений программы содержит числа 11 и 13?» — обязательное прохождение через одно или несколько чисел;
«Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?» — обязательное и запрещённое число сразу;
«Сколько существует программ, для которых при исходном числе 50 результатом является число 1, и при этом траектория вычислений содержит число 20 и не содержит 10?» — то же сочетание условий, но у команд другое направление (число убывает, а не растёт).

Дочитывать вопрос нужно до последнего слова: одна перепутанная частица «не» между «содержит» и «не содержит» превращает верный ход решения в неверный ответ, при этом сама арифметика не намекнёт на ошибку — оба варианта решаются одинаково гладко.

В демоверсии 2027 года ФИПИ поставил на эту позицию четвёртый подтип: условий на траекторию нет вовсе, зато одна из команд применима не к каждому числу.

Задание 13

Демоверсия ЕГЭ 2027 по информатике

Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды:

A. Прибавь 1 — увеличивает число на экране на 1;
B. Поменяй местами — меняет местами цифры двух младших разрядов; команда применима только к числу, у которого цифра в разряде десятков меньше цифры в разряде единиц.

Сколько существует программ, которые исходное число 100 преобразуют в число 141?

Ответ: 16.

Метод тот же самый. Считайте $d[n]$ — число программ, ведущих из $n$ в 141, — и идите от 141 вниз: $d[141]=1$ , а для остальных $n < 141$ берите $d[n]=d[n+1]$ плюс $d[B(n)]$ , если команда B к числу $n$ применима. Условие применимости команды — это ровно то же самое, что запрещённое число: оно просто вырезает часть переходов, а не часть вершин.

Как записывается ответ. Ответ на задание 13 — это одно число: количество программ. Никаких слов «программ», единиц измерения и самих программ (букв) в ответе быть не должно — только число, без пробелов и разделителей. Ответы в банке нередко бывают трёх- и четырёхзначными (100, 360, 1620, 4085) — «некрасивое» большое число не повод искать ошибку в арифметике, скорее в этом и есть смысл задания: посчитать то, что руками пересчитать нереально.

Теория: всё, что нужно для задания 13

Программа, команда, траектория

Команда — правило, которое переводит текущее число $x$ в новое число: «прибавь $k$ » даёт $x+k$ , «умножь на $k$ » даёт $k \cdot x$ , «раздели нацело на $k$ » даёт $\lfloor x/k \rfloor$ .
Программа — последовательность команд, применённых одна за другой к исходному числу $A$ .
Траектория вычислений — последовательность результатов выполнения каждой команды программы. Стартовое число $A$ в траекторию не входит, а последнее число траектории — это результат работы всей программы, то есть $B$ .
Пример из условия: программа ACB (A — прибавить 1, C — умножить на 2, B — прибавить 2) для исходного числа 7 даёт траекторию 8, 16, 18 — именно три числа, ровно по одному на каждую из трёх команд.
«Траектория содержит число $n$ » значит: где-то в этой последовательности результатов есть $n$ , причём $n$ может совпадать и с конечным числом $B$ — оно тоже часть траектории.

Метод: динамическое программирование по числам

Обозначим через $K(n)$ количество программ, которые переводят число $n$ в заданное конечное число (обозначим его $F$ , чтобы не путать с исходным числом всей задачи $A$ ). Метод — два правила.

Правило 1 (база). В конечном числе — единица:

K(F) = 1

Единственная программа, которая переводит $F$ в $F$ , — пустая (ноль команд). Если поставить 0, вся конструкция обнулится.

Правило 2 (переход). Число программ из $n$ — это сумма чисел программ из всех состояний, куда можно попасть одной командой:

K(n) = \sum_{c} K\big(c(n)\big)

где сумма берётся по всем командам $c$ исполнителя, а $c(n)$ — результат применения команды $c$ к числу $n$ . Слагаемое не учитывается (то есть равно 0), если $c(n)$ уже «перепрыгнуло» мимо $F$ и вернуться назад нельзя.

Маленький пример целиком

Пусть у исполнителя три команды — «прибавь 1», «прибавь 2», «умножь на 2» — и нужно перевести число 2 в число 10, без дополнительных условий. Считаем $K(n)$ от $n=10$ (база) в сторону уменьшения $n$ , потому что все команды только увеличивают число, а значит любая программа из $n$ сначала идёт в состояние больше $n$ , которое к этому моменту уже посчитано:

$n$	10	9	8	7	6	5	4	3	2
$K(n)$	1	1	2	3	5	9	16	30	62

Проверка на паре ячеек: $K(8) = K(9) + K(10) + K(16)$ . Из 8 команда «+1» даёт 9 ( $K=1$ ), «+2» даёт 10 ( $K=1$ ), «×2» даёт 16 — это уже больше 10, значит вклад 0. Итого $K(8) = 1 + 1 + 0 = 2$ . А $K(2) = K(3) + K(4) + K(4) = 30 + 16 + 16 = 62$ — команды «+2» и «×2» из числа 2 обе ведут в 4, и это два разных слагаемых, а не одно.

Обязательное промежуточное число: произведение участков

Пусть нужно перевести $A$ в $B$ , и траектория обязана содержать число $M$ , лежащее строго между $A$ и $B$ по направлению работы команд. Раз $M$ обязательно встретится, любая подходящая программа однозначно разрезается на два независимых куска: $A \to M$ и $M \to B$ . И наоборот — любой первый кусок можно склеить с любым вторым, получится ровно одна подходящая программа. Значит, количества нужно не складывать, а перемножать:

K_{A \to B,\ \text{через } M} = K_{A \to M} \cdot K_{M \to B}

Каждый множитель считается отдельной, независимой расстановкой: сначала конечным числом объявляется $M$ и считается $K_{A \to M}$ , затем конечным числом объявляется $B$ , а начальным — $M$ , и считается $K_{M \to B}$ .

На маленьком примере: пусть в траектории $2 \to 10$ (команды «+1», «+2», «×2») обязательно должно быть число 6. Тогда

K_{2 \to 6} = 8, \qquad K_{6 \to 10} = 5, \qquad K_{2 \to 10,\ \text{через } 6} = 8 \cdot 5 = 40.

Если обязательных чисел несколько и все они упорядочены между $A$ и $B$ (как 11 и 13 между 4 и 15 в примере из открытого банка ниже), участков становится три, а не два, и в произведении — три множителя. Порядок обязательных чисел в этом произведении всегда должен совпадать с порядком, в котором они реально идут по направлению работы команд.

Запрещённое число: обнуляем его в рекурсии

Если траектория не должна содержать число $Z$ , метод не меняется — меняется одна строчка в определении $K$ . Достаточно объявить, что через запрещённое число «программ 0»:

K(Z) = 0

а дальше как обычно: $K(F) = 1$ , $K(n) = \sum_c K(c(n))$ для всех остальных $n$ . Смысл прозрачен: раз через $Z$ «нельзя», то любая программа, которая туда всё-таки попадает, автоматически бракуется — а обнулив $K(Z)$ , вы гарантируете, что она не прибавится ни к одной сумме дальше по цепочке.

На том же примере ( $2 \to 10$ , команды «+1», «+2», «×2»), но с запретом на число 7:

K(10) = 1
K(9)  = K(10) + K(11) + K(18) = 1 + 0 + 0 = 1
K(8)  = K(9)  + K(10) + K(16) = 1 + 1 + 0 = 2
K(7)  = 0                              (запрещено)
K(6)  = K(7)  + K(8)  + K(12) = 0 + 2 + 0 = 2
K(5)  = K(6)  + K(7)  + K(10) = 2 + 0 + 1 = 3
K(4)  = K(5)  + K(6)  + K(8)  = 3 + 2 + 2 = 7
K(3)  = K(4)  + K(5)  + K(6)  = 7 + 3 + 2 = 12
K(2)  = K(3)  + K(4)  + K(4)  = 12 + 7 + 7 = 26

Без запрета ответ был 62, с запретом на 7 — 26: запрет отсекает больше трети программ, потому что число 7 в этой сетке команд оказывается «узким горлышком», через которое обычно проходит много траекторий.

Оба условия сразу: сначала разрежьте, потом обнулите

Когда в условии есть и обязательное число $M$ , и запрещённое $Z$ , приёмы просто складываются, но применять их нужно в правильном порядке:

сначала разрежьте задачу по обязательному числу $M$ на независимые участки $A \to M$ и $M \to B$ ;
затем в каждом из двух участков, где может встретиться запрещённое число $Z$ , поставьте $K(Z) = 0$ — запрет действует на всей траектории целиком, а не только в одном из кусков;
перемножьте два получившихся количества.

Пример из открытого банка: исходное число 1, конечное 35, команды «+1» и «×2», траектория обязана содержать 10 и не должна содержать 17. Разрезаем по 10:

K_{1 \to 35,\ \text{через }10,\ \text{без }17} = K_{1 \to 10} \cdot K_{10 \to 35,\ \text{без }17}.

Заметьте: запрет на 17 нужно учесть только во втором участке ( $10 \to 35$ ) — число 17 всё равно не может встретиться на участке $1 \to 10$ , потому что все числа там не превышают 10, а команды только увеличивают число. Но если бы участок «мог» дотянуться до 17, обнулять запрещённое число нужно было бы в обеих частях — проверяйте это диапазоном чисел на участке, а не полагайтесь на то, что запрет «уже учтён» глобально.

Почему нельзя считать «наоборот» не глядя на команды

В примерах выше рекурсия всегда была одна и та же — $K(n) = \sum_c K(c(n))$ , а условие обрыва — « $n$ перепрыгнуло конечное число — 0». Это работает только потому, что во всех этих задачах команды строго увеличивают число: числа только растут, значит траектория никогда не повторяется, а условие обрыва логично — «дальше, чем нужно, вернуться нельзя».

В банке встречаются и задания с обратным направлением: команды «вычти 1» и «раздели нацело на 2» только уменьшают число. Тогда исходное число больше конечного (например, 50 и 1), и условие обрыва меняется на противоположное:

K(F) = 1, \qquad K(n) = 0 \text{ при } n < F, \qquad K(n) = \sum_c K\big(c(n)\big).

Если механически скопировать условие « $n > F$ — обрыв» из задачи с растущими числами в задачу с убывающими командами, рекурсия либо никогда не остановится, либо тихо вернёт неверный (заниженный) ответ — программа не упадёт с ошибкой, а просто посчитает не то.

Правило одно: прежде чем писать рекурсию, определите, строго ли растут или строго ли убывают числа при применяемых командах на нужном диапазоне. Если команды смешанные (есть и увеличивающие, и уменьшающие), числа могут повторяться в траектории, а формулу «одно обращение — обрыв» напрямую применять уже нельзя: такие задачи в текущем банке задания 13 не встречаются, но при чтении условия направление всегда стоит проверять явно, а не предполагать по умолчанию.

Код на Python: итеративно и через lru_cache

Оба варианта ниже реализуют один и тот же метод, дают одинаковый результат и запускаются прямо в среде программирования на экзамене. Итеративная версия явно строит таблицу $K$ от конечного числа к начальному — так удобнее для задач с растущими числами:

def count_programs_iterative(start, finish, forbidden=()):
    K = {finish: 1}
    for n in range(finish - 1, start - 1, -1):
        if n in forbidden:
            K[n] = 0
            continue
        total = 0
        for nxt in (n + 1, n + 2, 2 * n):
            if nxt in K:
                total += K[nxt]
        K[n] = total
    return K[start]

Рекурсивная версия с $\text{lru\_cache}$ короче и не требует заранее знать направление команд — она сама останавливается, как только число превысило конечное:

from functools import lru_cache

def count_programs_recursive(start, finish, forbidden=()):
    @lru_cache(None)
    def K(n):
        if n in forbidden:
            return 0
        if n > finish:
            return 0
        if n == finish:
            return 1
        return K(n + 1) + K(n + 2) + K(2 * n)
    return K(start)

Обязательное число учитывается вызовом функции дважды с перемножением результатов, запрещённое — параметром $\text{forbidden}$ :

print(count_programs_recursive(2, 10))              # 62, без условий
print(count_programs_recursive(2, 6) *
      count_programs_recursive(6, 10))               # 40, обязательно через 6
print(count_programs_recursive(2, 10, forbidden=(7,)))  # 26, без числа 7

Все три числа (62, 40, 26) в этой статье получены запуском именно этого кода и совпадают с ручными таблицами выше.

Алгоритм решения задания 13

Выпишите команды исполнителя как функции числа. «Прибавь $k$ » — это $x \mapsto x + k$ , «умножь на $k$ » — $x \mapsto k \cdot x$ , «раздели нацело на $k$ » — $x \mapsto \lfloor x/k \rfloor$ .
Определите направление. Все команды увеличивают число, все уменьшают, или они смешанные? От этого зависит условие обрыва рекурсии и то, в какую сторону вести таблицу $K$ (см. блок про направление выше).
Выпишите обязательные и запрещённые числа из условия и отметьте их место на числовой прямой между $A$ и $B$ .
Разрежьте задачу по обязательным числам на независимые участки, идущие в порядке движения от $A$ к $B$ .
На каждом участке посчитайте $K$ — вручную таблицей (если диапазон небольшой) или кодом с $\text{lru\_cache}$ (если диапазон большой). Там, где запрещённое число попадает в диапазон участка, поставьте для него $K = 0$ .
Перемножьте результаты участков — не складывайте. Если участок один (обязательных чисел нет), просто возьмите единственное значение $K(A)$ .
Проверьте ответ на маленьком случае. Возьмите часть диапазона, посчитайте её полным перебором вручную (5–10 программ) и сверьте с формулой — это быстрее, чем искать ошибку в готовом большом ответе.

Доведите метод до автоматизма

Прорешайте 10–15 заданий подряд — и разбиение на участки с перемножением станет таким же рефлексом, как таблица умножения. Задания ЕГЭ по информатике из банка ФИПИ с проверкой ответа — на Repet.ai.

Открыть тренажёр

Примеры с разбором

Пример 1. Два обязательных числа — три независимых участка

Пример задания

Реальное задание из открытого банка ФИПИ

«Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A) Прибавить 1, B) Прибавить 2, C) Умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 15, и при этом траектория вычислений программы содержит числа 11 и 13? Траектория должна содержать оба указанных числа.»

Решение

Команды «+1», «+2», «×2» только увеличивают число, значит числа в траектории строго растут и не повторяются. Оба обязательных числа лежат в диапазоне: $4 < 11 < 13 < 15$ , поэтому любая подходящая программа однозначно разрезается на три независимых участка: $4 \to 11$ , $11 \to 13$ , $13 \to 15$ .

Участок $4 \to 11$ — считаем таблицей от 11 вниз к 4:

n     11  10   9   8   7   6   5   4
K(n)   1   1   2   3   5   8  14  25

Например, $K(9) = K(10) + K(11) + K(18) = 1 + 1 + 0 = 2$ , а $K(4) = K(5) + K(6) + K(8) = 14 + 8 + 3 = 25$ .

Участок $11 \to 13$ : удвоение из 11 даёт 22 — перелёт мимо 13, значит работают только «+1» и «+2»: $K(13) = 1$ , $K(12) = 1$ , $K(11) = K(12) + K(13) = 1 + 1 = 2$ (это программы «AA» и «B»).

Участок $13 \to 15$ устроен так же: $K(13) = 2$ (программы «AA» и «B»).

Перемножаем: $25 \cdot 2 \cdot 2 = 100$ .

print(count_programs_recursive(4, 11) *
      count_programs_recursive(11, 13) *
      count_programs_recursive(13, 15))

Ответ: 100. Проверка здравым смыслом: между 11 и 13 удвоение бесполезно (перелёт), поэтому там ровно столько же программ, сколько между 13 и 15 — оба множителя закономерно совпали (2 и 2), а основную часть комбинаторики даёт длинный участок от 4 до 11.

Пример 2. Обязательное и запрещённое число вместе

Пример задания

Реальное задание из открытого банка ФИПИ

«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: 1) Прибавить 1, 2) Умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?»

Решение

Обе команды («+1», «×2») увеличивают число, поэтому траектория строго растёт. Обязательное число 10 лежит между 1 и 35, значит задача разрезается на два независимых участка: $1 \to 10$ и $10 \to 35$ . Запрет на 17 нужно учесть только там, где 17 вообще может встретиться, — а это участок $10 \to 35$ : на участке $1 \to 10$ все числа не превышают 10, и 17 туда попасть не может в принципе.

Участок $1 \to 10$ (без ограничений):

n     10   9   8   7   6   5   4   3   2   1
K(n)   1   1   1   1   1   2   3   4   7  14

Здесь удвоение из любого $n \ge 6$ сразу даёт число больше 10, поэтому для 6, 7, 8, 9 работает только «+1», отсюда единицы в таблице. Итого $K(1) = 14$ .

Участок $10 \to 35$ с запретом на 17: для $n \ge 18$ удвоение уже даёт больше 35, так что $K(n) = 1$ для всех $n = 18, \dots, 35$ . Дальше $K(17) = 0$ (запрещено), и считаем вниз:

n     18  17  16  15  14  13  12  11  10
K(n)   1   0   1   2   3   4   5   6   7

Например, $K(16) = K(17) + K(32) = 0 + 1 = 1$ , $K(15) = K(16) + K(30) = 1 + 1 = 2$ , и так далее до $K(10) = K(11) + K(20) = 6 + 1 = 7$ .

Перемножаем: $14 \cdot 7 = 98$ .

from functools import lru_cache

def count_2cmd(start, finish, forbidden=()):
    @lru_cache(None)
    def K(n):
        if n in forbidden:
            return 0
        if n > finish:
            return 0
        if n == finish:
            return 1
        return K(n + 1) + K(2 * n)
    return K(start)

print(count_2cmd(1, 10) *
      count_2cmd(10, 35, forbidden=(17,)))

Ответ: 98. Проверка здравым смыслом: без запрета на 17 участок $10 \to 35$ дал бы $K(10) = 9$ (на 2 больше — ровно столько программ обязаны пройти через 17: сначала одним способом дойти от 10 до 17, а затем любым из двух способов — от 17 до 35). Без запрета весь ответ был бы $14 \cdot 9 = 126$ ; запрет вычитает $14 \cdot 2 = 28$ программ, идущих через 17, и остаётся $126 - 28 = 98$ .

Пример 3. Число убывает: команды с обратным направлением

Пример задания

Реальное задание из открытого банка ФИПИ

«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: А) Вычти 1, Б) Найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 50 результатом является число 1, и при этом траектория вычислений содержит число 20 и не содержит 10?»

Решение

Здесь обе команды уменьшают число — «вычти 1» и «целая часть от деления на 2». Значит, траектория строго убывает, исходное число (50) больше конечного (1), и условие обрыва рекурсии — обратное тому, что было в примерах 1 и 2: программ «0», если $n$ оказалось меньше конечного числа, а не больше. Если по инерции скопировать условие « $n > F$ — обрыв» из предыдущих примеров, счёт просто не остановится.

Обязательное число 20 разрезает задачу на два участка: $50 \to 20$ и $20 \to 1$ . Запрещённое число 10 не может встретиться на первом участке (там все числа не меньше 20), поэтому запрет учитываем только во втором.

from functools import lru_cache

def count_down(start, finish, forbidden=()):
    @lru_cache(None)
    def K(n):
        if n in forbidden:
            return 0
        if n < finish:
            return 0
        if n == finish:
            return 1
        return K(n - 1) + K(n // 2)
    return K(start)

print(count_down(50, 20))               # участок 50 -> 20
print(count_down(20, 1, forbidden=(10,)))  # участок 20 -> 1, без числа 10
print(count_down(50, 20) * count_down(20, 1, forbidden=(10,)))

Обратите внимание: условие обрыва теперь $n < finish$ , а не $n > finish$ — это прямое следствие того, что команды уменьшают число, а не увеличивают.

Результат: $K_{50 \to 20} = 12$ , $K_{20 \to 1,\ \text{без }10} = 135$ . Перемножаем: $12 \cdot 135 = 1620$ .

Ответ: 1620. Проверка здравым смыслом: без запрета на 10 участок $20 \to 1$ давал бы 195 — запрет вычитает ровно 60 программ, проходящих через 10 ( $K_{20 \to 10} \cdot K_{10 \to 1} = 2 \cdot 30 = 60$ ), и остаётся 135. Сама величина ответа (четырёхзначное число) ожидаема — на длинном убывающем участке 20 → 1 команда «вычти 1» и команда «÷2» комбинируются очень большим числом способов, это типично для заданий 13 с делением пополам.

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

Перепутали «содержит» и «не содержит»
Дочитывайте вопрос до конца и подчёркивайте частицу «не». И «содержит 10», и «не содержит 10» решаются одним и тем же методом с одинаково гладкой арифметикой — ошибка в частице никак не выдаёт себя на этапе счёта, а всплывает только на сверке с эталоном.
Забыли обнулить запрещённое число
Если в рекурсии нет явной проверки $n \in \text{forbidden}$ (или строчки $K(Z) = 0$ в ручной таблице), запрет просто не работает, и ответ совпадёт с обычным подсчётом без ограничений — на маленьких примерах разница в пару программ легко теряется незамеченной.
Сложили участки вместо того, чтобы перемножить
Обязательное промежуточное число разбивает программу на два (или больше) последовательных куска, и любой первый кусок сочетается с любым вторым — отсюда произведение, а не сумма. Сумма была бы верна, только если бы участки были альтернативными путями к одной и той же цели, а не последовательными этапами одной программы.
Скопировали условие обрыва рекурсии не глядя на направление команд
« $n > F$ — обрыв» верно только для команд, увеличивающих число. Если команды уменьшают число (как «вычти 1» или «раздели на 2»), условие обрыва — $n < F$ . Спутав их, вы либо получите бесконечную рекурсию, либо тихо посчитаете 0 там, где ответ положительный.
Забыли, что одинаковый результат от разных команд — это разные слагаемые
Если команда «+2» и команда «×2» из одного и того же числа дают одно и то же следующее состояние, в сумме $K(n) = \sum_c K(c(n))$ это всё равно два отдельных слагаемых, а не одно — это разные команды, значит и разные программы.
Учли запрет только в одном из двух участков
Если запрещённое число теоретически может встретиться в обеих частях разреза (а не только в одной, как в примере 2 и 3 этой статьи), $K(Z) = 0$ нужно поставить в каждой из отдельных расстановок — запрет действует на всю траекторию целиком, а не на выбранный кусок.
Попытались перебрать программы вручную
На дистанциях в 10–30 шагов количество программ измеряется сотнями и тысячами (100, 1620, 4085 — реальные ответы из банка). Перебор вручную не укладывается в 7 минут и почти гарантированно теряет часть программ. Метод $K(n)$ — единственный практичный вариант.

Как задание 13 связано с остальным экзаменом

Всего в КИМ ЕГЭ по информатике 27 заданий, все — с кратким ответом, экзамен сдаётся за компьютером. Максимальный первичный балл — 29, на всю работу отводится 235 минут. Задание 13 занимает в этой конструкции особое место:

оно входит в раздел «Алгоритмы и программирование» вместе с заданиями 5, 6, 12, 16, 17, 24, 25, 26 — это девять заданий и десять первичных баллов;
делит элемент содержания 3.3 с заданием 5 и заданием 6 — там тот же формальный исполнитель, но программа короткая и решается прямым прогоном без всякого программирования (базовый уровень);
стоит в одном смысловом ряду с заданием 12 — тоже повышенный уровень, тоже исполнитель с фиксированным набором команд, но там объект — строка, а не число, и метод другой (инвариант и прогон на коротких строках, а не динамическое программирование);
приём «динамическое программирование по числам» — тот же математический инструмент, что используется в задачах на рекуррентные соотношения (задание 16): и там, и там значение в точке считается через уже посчитанные значения в соседних точках;
в варианте 2027 года оно стоит между заданием 12 и заданием 14 (позиционные системы счисления) — три задания повышенного уровня подряд, на которые вместе отводится 16 минут.

Задание 5 — формальный исполнитель, базовый уровень Задание 6 — управление исполнителем Задание 12 — исполнитель Редактор Задание 14 — позиционные системы счисления Задание 16 — рекуррентные выражения Все задания ЕГЭ по информатике

План подготовки на 2 недели

Неделя 1 — ставим метод

День 1–2: разберите метод $K(n)$ на маленьких примерах (диапазон 5–15 чисел, одна-две команды) — считайте вручную таблицей и обязательно проверяйте полным перебором программ, пока приём не станет понятным правилом, а не «магией». День 3–4: добавьте обязательное промежуточное число и потренируйте разрезание на участки с перемножением. День 5–7: добавьте запрещённое число, а также сочетание обоих условий сразу — на тех же маленьких диапазонах, где ответ можно перепроверить руками.

Неделя 2 — код, направление, скорость

День 1–2: перепишите метод в код на Python с $\text{lru\_cache}$ — это и быстрее руками писать на экзамене, и надёжнее для больших диапазонов. День 3–4: прорешайте задания с обеими командами возрастания и обеими командами убывания (как в примере 3 этой статьи), каждый раз заранее проговаривая направление и условие обрыва рекурсии, прежде чем писать код. День 5–7: работайте на время — не больше 7 минут на задание, включая написание и запуск программы, и проверьте себя в тренажёре на заданиях из банка ФИПИ.

Проверьте себя на реальных заданиях

На Repet.ai собраны задания ЕГЭ по информатике из открытого банка ФИПИ. Решайте онлайн, проверяйте ответ мгновенно и разбирайте решение — бесплатно.

Перейти к практике

Частые вопросы

Часто задаваемые вопросы