Задание 12 ЕГЭ по информатике: исполнитель Редактор

Задание 12 ЕГЭ по информатике (КЕГЭ) — это исполнитель с фиксированным набором команд: чаще всего перед вами строковый редактор с двумя командами — заменить(v, w) и нашлось(v) — и программа с циклом ПОКА, которая гоняет их по входной строке. По кодификатору это проверяемый элемент содержания 3.3, задание повышенного уровня сложности, за него дают 1 первичный балл, файла к нему не прилагается, и специализированное программное обеспечение не требуется. Ответ — число: либо результирующая строка, записанная цепочкой цифр, либо количество нужных цифр в ней, либо параметр входа, при котором выполняется заданное условие. В статье — точная семантика команд, три рабочих приёма (инвариант, прогон на коротких строках, эмулятор на Python) и три разбора реальных заданий из открытого банка ФИПИ с проверенными ответами. Потренироваться можно на реальных заданиях 12 ЕГЭ по информатике онлайн — с мгновенной проверкой ответа.

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

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

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

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

Дальше идёт сама программа и вопрос — он бывает трёх видов, и от вида вопроса зависит, что именно писать в ответ:

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

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

ПОКА нашлось (1111) ИЛИ нашлось (8888)
   ЕСЛИ нашлось (1111)
      ТО заменить (1111, 8)
      ИНАЧЕ заменить (8888, 11)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

ПОКА нашлось (2111) ИЛИ нашлось (1112)
   заменить (111, 1)
   ЕСЛИ нашлось (21)
      ТО заменить (21, 12)
      ИНАЧЕ заменить (12, 1)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

8888 нашлось, 1111 нет → заменить (8888, 11):
   получаем "11" и (n - 4) восьмёрок

снова 8888 нашлось (единиц пока только 2) → заменить (8888, 11):
   получаем "1111" и (n - 8) восьмёрок

теперь нашлось (1111) → заменить (1111, 8):
   получаем "8" и (n - 8) восьмёрок

def nashlos(s, v):
    return v in s

def zamenit(s, v, w):
    return s.replace(v, w, 1)

s = "8" * 82
while nashlos(s, "1111") or nashlos(s, "8888"):
    if nashlos(s, "1111"):
        s = zamenit(s, "1111", "8")
    else:
        s = zamenit(s, "8888", "11")
print(s)
print(len(s))

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

1. Определите вид вопроса. Нужна вся результирующая строка, количество определённой цифры в ней или значение параметра входа (обычно $n$), при котором выполняется дополнительное условие — от этого зависит, что именно вы будете подставлять в ответ.
2. Выпишите тело цикла отдельно, сохраняя точный порядок команд сверху вниз. Отметьте: это взаимоисключающие ветки ЕСЛИ/ИНАЧЕ или независимые команды подряд, где за одну итерацию может произойти несколько замен.
3. Прогоните программу вручную на коротком входе — строке из 4–10 символов того же вида, что в условии — и выпишите 3–4 первые итерации целиком, посимвольно.
4. Проверьте инвариант. Как каждая замена меняет длину строки, сумму цифр или количество нужной цифры? Если один «служебный» символ движется вдоль строки, перепишите каждую цифру по фиксированному правилу — и посчитайте итог напрямую, без моделирования всей строки.
5. Если прямой формулы нет, прогоните программу на нескольких коротких входах одного семейства ($n = 4, 8, 12, 16, \dots$) и найдите период или закономерность, сводящую большое $n$ к уже посчитанному маленькому случаю.
6. Для полной надёжности напишите эмулятор на Python с командой заменить(v, w) как $\text{s.replace(v, w, 1)}$, запустите его на реальных числах из условия и сверьте с результатом, полученным вручную.
7. Запишите ответ числом — без пробелов, кавычек и слова «строка»: либо саму результирующую строку цифр, либо счётчик, либо найденный параметр.

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

Пример 1. Инвариант: «бегущий» символ переписывает цифры

НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
   ЕСЛИ нашлось (>1)
      ТО заменить (>1, 22>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>2)
      ТО заменить (>2, 2>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>0)
      ТО заменить (>0, 1>)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

>0 → 1>   цифра 0 становится 1, вклад в сумму: 1
>1 → 22>  цифра 1 становится 22, вклад в сумму: 2 + 2 = 4
>2 → 2>   цифра 2 остаётся 2 (символ просто идёт дальше), вклад: 2

n = 0: 117 = 9 · 13         — составное
n = 1: 121 = 11 · 11        — составное
n = 2: 125 = 5 · 25         — составное
n = 3: 129 = 3 · 43         — составное
n = 4: 133 = 7 · 19         — составное
n = 5: 137                  — простое

Пример 2. Прогон на коротких входах: период длиной 8

НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (8888)
   ЕСЛИ нашлось (1111)
      ТО заменить (1111, 8)
      ИНАЧЕ заменить (8888, 11)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

есть 8888, нет 1111 → заменить (8888, 11):
   "11" + (n - 4) восьмёрок

снова есть 8888 (единиц только 2, это не 1111) → заменить (8888, 11):
   "1111" + (n - 8) восьмёрок

теперь есть 1111 → заменить (1111, 8):
   "8" + (n - 8) восьмёрок

def nashlos(s, v):
    return v in s

def zamenit(s, v, w):
    return s.replace(v, w, 1)

s = "8" * 82
while nashlos(s, "1111") or nashlos(s, "8888"):
    if nashlos(s, "1111"):
        s = zamenit(s, "1111", "8")
    else:
        s = zamenit(s, "8888", "11")

print(s)

Пример 3. Когда нужен полноценный эмулятор: перебор по n

НАЧАЛО
ПОКА нашлось (31) ИЛИ нашлось (411) ИЛИ нашлось (1111)
   ЕСЛИ нашлось (31)
      ТО заменить (31, 1)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (411)
      ТО заменить (411, 13)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (1111)
      ТО заменить (1111, 4)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

def nashlos(s, v):
    return v in s

def zamenit(s, v, w):
    return s.replace(v, w, 1)

def run(n):
    s = "4" + "1" * n
    while nashlos(s, "31") or nashlos(s, "411") or nashlos(s, "1111"):
        if nashlos(s, "31"):
            s = zamenit(s, "31", "1")
        if nashlos(s, "411"):
            s = zamenit(s, "411", "13")
        if nashlos(s, "1111"):
            s = zamenit(s, "1111", "4")
    return s

for n in range(4, 10000):
    result = run(n)
    digit_sum = sum(int(c) for c in result)
    if digit_sum == 34:
        print(n, result, digit_sum)
        break

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

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

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

• оно входит в раздел кодификатора «Алгоритмы и программирование» — это 9 заданий и 10 первичных баллов на всю работу (задания 5, 6, 12, 16, 17, 23, 24, 25, 26);
• делит проверяемый элемент содержания КЭС 3.3 с тремя другими заданиями — заданием 5 и заданием 6 (оба базового уровня, программы там короче и без параметра $n$), и заданием 23 (тоже повышенный уровень, но там уже числовой, а не строковый исполнитель, и вопрос идёт про ход выполнения, а не про конечный результат);
• приём «написать эмулятор на Python и запустить» — прямой предшественник заданий 24, 25 и 26, где программа сложнее (10–20 строк), а два из них — 24 и 26 — дополнительно работают с приложенным файлом, но идея та же: смоделировать исполнителя точно по описанию, а не пытаться угадать результат;
• а метод поиска инварианта, отработанный на задании 12, напрямую переносится на задание 16 (рекуррентные выражения) — там тоже выгоднее сначала понять закономерность, чем вычислять всё подряд.

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

Неделя 1 — семантика команд и ручное моделирование

День 1–2: выучите наизусть точные формулировки заменить(v, w) и нашлось(v) — что каждая делает и чего не делает. День 3–4: прогоняйте вручную на бумаге программы из 4–6 строк на коротких строках (6–10 символов), записывая состояние строки после каждой отдельной команды, а не после всего тела цикла. День 5–7: научитесь на глаз отличать конструкцию ЕСЛИ/ИНАЧЕ (одна замена за итерацию) от последовательности независимых ЕСЛИ (возможно несколько замен за итерацию) — берите задания вперемешку и сначала классифицируйте тело цикла, и только потом считайте.

Неделя 2 — инвариант и прогон на коротких входах

День 1–3: на каждой новой программе сначала проверяйте три кандидата в инварианты — длину строки, сумму цифр, количество конкретной цифры — и смотрите, меняются ли они по единому правилу независимо от того, какая замена сработала. День 4–5: если инварианта нет, тренируйтесь строить таблицу «вход → результат» для маленьких $n$ и находить период. День 6–7: решайте одну и ту же задачу двумя способами — предполагаемым инвариантом или найденным периодом, а затем эмулятором на Python — и сверяйте. Расхождение — сигнал, что найденная закономерность не работает для всех $n$.

Неделя 3 — эмулятор, скорость, полный банк

День 1–3: напишите универсальный шаблон эмулятора (функции нашлось и заменить через $\text{s.replace(v, w, 1)}$), под который легко подставлять новую программу и новый вход, и отработайте на нём поиск наименьшего/наибольшего $n$ перебором. День 4–5: решайте задания на время — не больше 6 минут на задание, включая перенос программы на бумагу или в эмулятор. День 6–7: пройдите оставшиеся задания КЭС 3.3 (5, 6, 23) вперемешку с заданием 12, чтобы закрепить семантику формального исполнителя как единый навык, и проверьте себя в тренажёре на заданиях из банка ФИПИ.