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

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

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

4 варианта с ответами

Время работы исполнителя делится на дискретные такты (шаги). В начальный момент времени головка находится в начальном состоянии q0. На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, и/или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Если пара «символ состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Сдвиг происходит после записи символа в текущую ячейку. Третий элемент новое состояние головки после выполнения команды. Приведём пример выполнения программы, заданной таблично. В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «1». Выполните задание. На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 12, условие
Ответ
999

Исполнитель обрабатывает строку символов. Он применяет к строке следующие команды замены, каждый раз выбирая первую подходящую по порядку и заменяя самое левое вхождение:

1. 78 → 9
2. 77 → 8

Если ни одна команда не применима, исполнитель останавливается.

На вход подана строка, содержащая 70 идущих подряд цифр 7, а затем 70 цифр 8. Определите, сколько символов «8» будет в строке после остановки исполнителя.

Ответ
103

Команды проверяются по порядку, поэтому первая из них имеет приоритет: пока в строке есть сочетание «78», работает только она.

Удобнее не прослеживать все шаги вручную, а заметить, что процесс конечен: каждая замена укорачивает строку, значит исполнитель обязательно остановится. Аккуратно применив правила до конца, получаем строку, в которой символ «8» встречается 103 раз. Ответ — 103.

Исполнитель обрабатывает строку символов. Он применяет к строке следующие команды замены, каждый раз выбирая первую подходящую по порядку и заменяя самое левое вхождение:

1. 12 → 3
2. 11 → 2

Если ни одна команда не применима, исполнитель останавливается.

На вход подана строка, содержащая 50 идущих подряд единиц, а затем 30 двоек. Определите, сколько символов «2» будет в строке после остановки исполнителя.

Ответ
53

Команды проверяются по порядку, поэтому первая из них имеет приоритет: пока в строке есть сочетание «12», работает только она.

Удобнее не прослеживать все шаги вручную, а заметить, что процесс конечен: каждая замена укорачивает строку, значит исполнитель обязательно остановится. Аккуратно применив правила до конца, получаем строку, в которой символ «2» встречается 53 раз. Ответ — 53.

Исполнитель обрабатывает строку символов. Он применяет к строке следующие команды замены, каждый раз выбирая первую подходящую по порядку и заменяя самое левое вхождение:

1. AB → C
2. AA → B

Если ни одна команда не применима, исполнитель останавливается.

На вход подана строка, содержащая 40 идущих подряд букв A, а затем 25 букв B. Определите, сколько символов «B» будет в строке после остановки исполнителя.

Ответ
43

Команды проверяются по порядку, поэтому первая из них имеет приоритет: пока в строке есть сочетание «AB», работает только она.

Удобнее не прослеживать все шаги вручную, а заметить, что процесс конечен: каждая замена укорачивает строку, значит исполнитель обязательно остановится. Аккуратно применив правила до конца, получаем строку, в которой символ «B» встречается 43 раз. Ответ — 43.

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

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

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

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

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

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

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

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

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

Ответ2221

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

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