Задание 12 ЕГЭ по информатике

Что проверяет: Исполнитель, обрабатывающий строку

Задание 12 ЕГЭ по информатике проверяет тему «исполнитель, обрабатывающий строку». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Ответ

999

Теория к заданию 12 ЕГЭ по информатике: исполнитель, обрабатывающий строку

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

Что нужно знать

Программа задаётся таблицей: строка соответствует состоянию головки, а столбец соответствует символу в текущей ячейке.
Команда состоит из записываемого символа, направления сдвига и нового состояния.
Символ «S» завершает работу исполнителя, «N» означает отсутствие сдвига.
Полезно проследить работу программы на короткой строке: закономерность обычно видна за несколько тактов.
Ответ часто сводится к арифметической зависимости между исходным и конечным числом символов.

Разбор программы исполнителя

Команда заменить (v, w) ищет первое слева вхождение цепочки v и заменяет его на w.
Команда нашлось (v) проверяет наличие цепочки и используется в условии цикла.
Цикл ПОКА нашлось (v) выполняется, пока в строке есть хотя бы одно вхождение.
Главный приём: отследить инвариант, то есть то, что сохраняется на каждом шаге (сумма цифр, количество символов, остаток).
Не прогоняйте длинную строку целиком: разберите короткий пример и найдите закономерность.
Часто программа сводит строку к остатку от деления количества символов на некоторое число.
Проверьте, что цикл завершается: если замена удлиняет строку, возможен бесконечный цикл.
В ответе обычно получается короткая строка, запишите её без пробелов.

Как решать задание 12

Разберите приведённый в условии пример, чтобы понять формат таблицы.
Выполните программу вручную на короткой модельной строке.
Сформулируйте, что именно программа делает со строкой.
Перенесите закономерность на строку из условия и составьте уравнение.
Найдите требуемое максимальное или минимальное значение.

Разбор примера

Программа: ПОКА нашлось (11) заменить (11, 2) КОНЕЦ ПОКА. Что получится из строки 1111111 (семь единиц)?

Замена меняет две единицы на цифру 2, то есть каждый шаг убирает одну единицу и добавляет двойку.
Шаг 1: 1111111 превращается в 211111.
Шаг 2: первое вхождение 11 теперь в конце после двойки: получаем 22111.
Шаг 3: получаем 2221.
Вхождений 11 больше нет: между двойками и одинокой единицей пары не образуется.
Цикл останавливается, в результате получается строка 2221.

Ответ2221

Частые ошибки

Меняют порядок действий: сдвиг происходит после записи символа.
Пытаются проследить всю тысячу тактов вместо поиска закономерности.

Задание 12 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.