Что делает программа, как понять её логику и как получить правильный ответ

Задание №12 — одно из самых «хитрых» в ЕГЭ по информатике.

Оно проверяет умение читать программу для исполнителя с лентой (по сути, мини-машины Тьюринга), понимать принцип её работы, а не просто механически подставлять значения.

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

Давай разберём, как решать такие задачи и почему правильный ответ для варианта 2026 — 999.

📘 1. Что проверяет 12 задание ЕГЭ

Задачи 12 номера направлены на умение:

  • анализировать табличное описание алгоритма,
  • понимать работу машины с лентой и состояниями,
  • отслеживать изменения символов (0, 1, λ),
  • делать вывод о возможных исходных данных.

Это задание — не про программирование на Python.

Это про логику алгоритмов → то, что нужно настоящему программисту.

📘 2. Как выглядит программа из ЕГЭ-2026 (простыми словами)

На ленте есть строка из 1000 символов — только 0 и 1.

Справа и слева — пустые ячейки λ.

Головка стоит справа от строки.

Таблица действий по состояниям:

λ 10q0λ, L, q1q1λ, S, q1 0, S, q1 1, L, q1

Расшифровка:

  • В q0 при виде λ → двигаемся влево и переходим в q1.
  • В q1:
  • если λ → конец работы;
  • если 1 → превращаем в 0 и останавливаемся;
  • если 0 → превращаем в 1 и идём левее.

Главная идея:

программа идёт справа, превращая подряд идущие справа 0 → 1, пока не встретит 1;

1 превращает в 0 — и останавливается.

То есть алгоритм инвертирует «хвост нулей» справа и меняет ближайшую слева единицу.

📘 3. Что делает алгоритм с числом?

(объяснение, которое реально помогает)

Представь, что у тебя есть набор из 0 и 1, например:

... 1 0 0 0 0

Эта программа:

  1. идёт справа налево,
  2. каждый 0 она превращает в 1 и идёт дальше,
  3. когда встречает 1, превращает его в 0 и останавливается.

То есть изменяется только хвост вида:

1 0 0 0 ... 0

Если там k нулей, то:

  • до алгоритма там было k нулей,
  • после — один ноль (потому что 1 превратился в 0).

Значит:

Нулей стало меньше на (k – 1).

📘 4. Выводим формулу «было → стало»

Пусть:

  • Z₀ — сколько нулей было,
  • Z₁ = 343 — сколько стало.

Тогда:

Отсюда:

То есть чем больше хвост из нулей (k), тем больше нулей было исходно.

📘 5. Ограничения

Всего символов — 1000.

Значит:

  • максимум нулей — 1000,
  • но число не может быть из 1000 нулей, потому что алгоритм тогда превратил бы все нули в единицы → нулей стало бы 0, а не 343.

Значит:

Подставляем максимальное k:

🎯 Итог

Максимальное возможное количество нулей в исходной строке:

⭐ 999

Это и есть правильное решение 12 задания ЕГЭ по информатике 2026.

🧠 Запомни лайфхак easyknow по 12 номеру:

Сначала пойми, что делает программа, а потом думай, какие данные могли привести к известному результату.

Задачи такого типа решаются не подбором, а чистой логикой.

Эта статья — лишь фрагмент знаний. На платформе Easyknow вся подготовка становится системой: от большой коллекции материалов по разным предметам до домашних заданий с проверкой. Всё в одном месте, по вашему личному плану.

Переходите на платформу и получите скидку 40% на первый месяц занятий с репетитором. Скидка активируется сразу после регистрации.