ЕГЭ 2026 · Задание 12

Выполнение алгоритмов для исполнителей

Редактор и машина Тьюринга: последовательные замены, состояния, головка и трассировка.

Повышенный уровеньИсполнители30–40 мин✓ Полный урок

Что нужно понимать

В Редакторе и машине Тьюринга результат определяется строгой последовательностью элементарных команд. Здесь особенно важно не делать несколько замен «одновременно».

→

Редактор

Обычно заменяется первое найденное слева вхождение, если условие не говорит иначе.

Состояние

У машины Тьюринга действие зависит одновременно от текущего символа и состояния.

▣

Лента

После записи символа головка может сдвинуться влево, вправо или остаться на месте.

Ключевая идея

Для длинной строки сначала выполните 3–5 шагов вручную. Часто становится видна закономерность, которую затем удобно подтвердить небольшим скриптом.

Надёжный алгоритм решения

Перепиши правила без сокращений

Зафиксируй порядок проверок и замен.

Сделай один шаг вручную

Отметь строку/ленту, позицию и состояние после действия.

Повторяй строго по условию

Не применяй два правила к одной версии строки одновременно.

Ищи инвариант

Количество символов, сумма цифр или число инверсий часто меняются предсказуемо.

Проверь результат

Для Редактора можно смоделировать replace(old,new,1), для Тьюринга — словарь правил.

Типичная ошибка: Самая частая ошибка — заменить все найденные подстроки сразу. В типовом алгоритме Редактора одна команда меняет только одно указанное вхождение.

Пошаговый разбор

Редактор выполняет: ПОКА в строке есть «12», ЗАМЕНИТЬ первое «12» на «21». Что получится из строки 111222 и сколько замен будет выполнено?

Идея · перестановкаИсходные данные

12 → 21

Каждая замена передвигает одну двойку на одну позицию влево относительно единицы.

ИнверсииРезультат

Есть 3 единицы и 3 двойки. Каждая двойка должна пройти мимо каждой единицы: 3 × 3 = 9 замен.

РазборОткрывай шаги по очереди

111222 → 112122 → 121122 → 211122 …

Число инверсий увеличивается на 1 после каждой замены, пока слева не окажутся все двойки.

Через 9 замен получаем 222111; подстроки «12» больше нет.

Тренажёр

Ответь на оба вопроса. Проверка работает прямо в браузере; правильные ответы автоматически отмечают практику выполненной.

Практика

Закрепи алгоритм

2 вопроса

Сколько замен 12→21 потребуется, чтобы превратить строку 1122 в строку без «12»?

Какой будет конечная строка для 1122 при таком алгоритме?

Шпаргалка на экзамен

Выполняй ровно одну команду на одном шаге.
Фиксируй порядок правил и первое/левое вхождение.
Для Тьюринга записывай тройку: состояние, символ, позиция головки.
Перед длинной симуляцией ищи закономерность или инвариант.

Урок 12 завершён

Продолжай по маршруту

Прогресс урока сохраняется локально в браузере.

← Задание 11 Задание 13 →

Тематика урока сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗