Задание 12 ЕГЭ по информатике проверяет умение выполнить алгоритм для формального исполнителя. В демоверсиях последних лет, включая проект демоверсии 2027 года, это исполнитель МТ — машина Тьюринга: головка ходит по ленте и переписывает символы по таблице команд. В вариантах и сборниках прошлых лет в этом номере встречался и исполнитель Редактор, который заменяет подстроки. По спецификации ФИПИ задание повышенного уровня, решается без компьютера, стоит 1 балл, на него отводится около 6 минут. Разберём оба исполнителя, начиная с машины Тьюринга.
Как устроена машина Тьюринга в задании 12
У исполнителя МТ есть бесконечная лента из ячеек. В каждой ячейке записан один символ, пустая ячейка обозначается $\lambda$. Над лентой стоит головка, и в каждый момент она находится в одном из состояний $q_0, q_1, q_2, \ldots$. Работа начинается в состоянии $q_0$.
Программа задаётся таблицей: строки — состояния, столбцы — символы. На пересечении стоит команда из трёх частей:
- какой символ записать в текущую ячейку (может совпадать с прежним);
- куда сдвинуться: L — влево, R — вправо, S — остановиться;
- в какое состояние перейти.
Например, команда «0, L, $q_3$» значит: записать в ячейку 0, сдвинуться на одну ячейку влево и перейти в состояние $q_3$. Сначала запись, потом сдвиг. Пустая клетка таблицы означает, что такая пара «состояние — символ» в работе программы не встречается.
Разбор задания 12 из демоверсии 2027
Условие. На ленте в соседних ячейках записано двоичное представление числа 2025 без ведущих нулей. Слева и справа — пустые ячейки $\lambda$. Головка стоит в ближайшей ячейке справа от числа в состоянии $q_0$. Программа:
| $\lambda$ | 0 | 1 | |
|---|---|---|---|
| $q_0$ | $\lambda$, L, $q_1$ | ||
| $q_1$ | 1, L, $q_2$ | 0, L, $q_1$ | 1, L, $q_1$ |
| $q_2$ | $\lambda$, S, $q_2$ |
Определите результат выполнения программы и запишите получившееся число в десятичной системе.
Решение. Сначала поймём смысл каждого состояния, а не будем шагать по ячейкам вслепую.
- $q_0$ видит пустую ячейку, ничего не меняет и делает шаг влево, на последнюю цифру числа. Переход в $q_1$.
- $q_1$ на цифрах 0 и 1 переписывает ту же цифру и идёт влево. Значит, число он не меняет, а просто проходит его до конца.
- Дойдя до пустой ячейки слева от числа, $q_1$ записывает туда 1 и переходит в $q_2$.
- $q_2$ сразу останавливает исполнителя.
Итог: программа приписывает к числу единицу слева.
Переведём 2025 в двоичную систему: $2025 = 11111101001_2$, это 11 цифр. Единица, приписанная слева, добавляет $2^{11} = 2048$:
$$ 111111101001_2 = 2048 + 2025 = 4073. $$
Ответ: 4073.
Как решать задание 12 с машиной Тьюринга
- Определите, откуда стартует головка и в какую сторону она пойдёт из $q_0$.
- Опишите словами каждое состояние: «идёт влево, ничего не меняя», «меняет 1 на 0 и идёт дальше», «останавливается». Обычно состояний 3–4, и у каждого простой смысл.
- Проверьте программу на коротком числе, например на $101_2$, — пять-шесть шагов вручную.
- Примените вывод к числу из условия и переведите результат в нужную систему счисления.
Типичные «смыслы» программ, которые полезно узнавать сразу:
| Что делает программа | Как меняется число |
|---|---|
| приписывает 1 слева к числу из $k$ цифр | $+2^k$ |
| приписывает 0 справа | $\times 2$ |
| заменяет все 1 на 0, а 0 на 1 | $2^k - 1 - n$ |
| идёт справа налево, меняет 1 на 0 до первого 0, который заменяет на 1 | $n + 1$ |
Пример. Программа идёт по числу справа налево. В $q_1$: на 1 пишет 0 и идёт влево, на 0 пишет 1 и останавливается, на $\lambda$ пишет 1 и останавливается. Это прибавление единицы: из 2025 получится 2026, а из $2047 = 11111111111_2$ получится $100000000000_2 = 2048$.
Симулятор машины Тьюринга на Python
Задание решается на бумаге, но на КЕГЭ компьютер под рукой, и ответ можно проверить. Программу из таблицы удобно записать словарём:
def run(program, tape_str, pos, state="q0", blank="λ", max_steps=10**6):
tape = dict(enumerate(tape_str)) # номер ячейки -> символ
for _ in range(max_steps):
sym = tape.get(pos, blank)
write, move, state = program[state][sym]
tape[pos] = write
if move == "S":
break
pos += 1 if move == "R" else -1
cells = [tape[i] for i in sorted(tape)]
return "".join(cells).strip(blank)
# демоверсия ЕГЭ 2027
program = {
"q0": {"λ": ("λ", "L", "q1")},
"q1": {"λ": ("1", "L", "q2"), "0": ("0", "L", "q1"), "1": ("1", "L", "q1")},
"q2": {"λ": ("λ", "S", "q2")},
}
s = bin(2025)[2:]
res = run(program, s, pos=len(s)) # головка — справа от числа
print(res, int(res, 2)) # 111111101001 4073
Позиция len(s) — это ячейка сразу справа от числа: цифры занимают ячейки с номерами от 0 до len(s) - 1. Где писать и запускать такой код на экзамене, мы разобрали в статье про среду разработки Python для ЕГЭ.
Исполнитель Редактор
В вариантах прошлых лет в задании 12 встречался исполнитель Редактор. Он работает со строкой и умеет две вещи: заменить(v, w) — заменить первое слева вхождение v на w, и нашлось(v) — проверить, есть ли v в строке.
Пример. К строке из 70 идущих подряд цифр 2 применили программу:
ПОКА нашлось(222) ИЛИ нашлось(888)
ЕСЛИ нашлось(222) ТО заменить(222, 8)
ИНАЧЕ заменить(888, 2)
КОНЕЦ ПОКА
Какая строка получится?
На Python Редактор пишется один-в-один: заменить — это replace с третьим аргументом 1, то есть замена только первого вхождения.
s = "2" * 70
while "222" in s or "888" in s:
if "222" in s:
s = s.replace("222", "8", 1)
else:
s = s.replace("888", "2", 1)
print(s) # 2282
Ответ: 2282.
Вручную такие задачи решают, отслеживая, как меняется количество символов за один «круг» программы, но при наличии компьютера код надёжнее.
Где теряют баллы
где теряют баллы
Путают порядок действий в команде: сначала символ записывается в текущую ячейку, и только потом головка сдвигается.
Где теряют баллы. Ошибаются при переводе в двоичную систему или обратно. Проверяйте перевод: $11111101001_2$ должно давать ровно 2025.
Где теряют баллы. Записывают ответ в двоичной системе, хотя в условии просят десятичную. Перечитайте последнюю строку задания.
Где теряют баллы. В Редакторе заменяют все вхождения сразу. Команда
заменитьменяет только первое слева, поэтому в Python нуженreplace(v, w, 1).
Задачи для самопроверки
Задача 1. Программа идёт справа налево по двоичной записи числа 2025 и заменяет каждую 1 на 0, а каждый 0 на 1, а дойдя до пустой ячейки, останавливается. Какое число получится? Ответ дайте в десятичной системе.
Задача 2. На ленте записано число 100 в двоичной системе, головка стоит слева от числа. Программа идёт вправо, не меняя цифр, а в первую пустую ячейку справа записывает 0 и останавливается. Какое число получится?
Задача 3. Число 2047 записано в двоичной системе. Программа прибавляет к нему единицу (как в примере выше). Сколько цифр будет в результате?
Ответы
Задача 1. Инвертирование 11-битного числа: $2^{11} - 1 - 2025 = 22$.
Задача 2. Приписанный справа 0 удваивает число: $200$.
Задача 3. $2047 + 1 = 2048 = 100000000000_2$ — 12 цифр.
Коротко о главном
В задании 12 ЕГЭ по информатике чаще всего встречается машина Тьюринга. Решение начинается не с механического прохода по ячейкам, а с вопроса: что делает каждое состояние? Обычно программа приписывает цифру, инвертирует число или прибавляет единицу, и ответ получается одной формулой. Для проверки на экзамене годится короткий симулятор на Python. Исполнитель Редактор из прошлых лет решается циклом с replace(v, w, 1). Ещё разборы первой части КЕГЭ — задание 2 и задание 7.
Если хотите разобрать все задания КЕГЭ по системе, с занятием раз в неделю и ежедневной практикой, посмотрите курс подготовки к ЕГЭ по информатике.
Разбор подготовил Максим Муратов, преподаватель информатики, математики и физики с 2009 года, 10 лет преподавал информатику в МФТИ. Об авторе
