Информатика. ЕГЭ

Перейти к заданиям

Задание 12. Информатика. ЕГЭ 2026. Демо

Просмотры: 6918
Изменено: 6 марта 2026

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов \(\boldsymbol{A = \{a_0, \, a_1, \, \ldots , \, a_{n-1}\})},\) включая специальный пустой символ \(\boldsymbol{a_0}.\)

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний \(\boldsymbol{Q = \{q_0, \, q_1, \, \ldots , \, q_{n-1} \}}.\) В начальный момент времени головка находится в начальном состоянии \(\boldsymbol{q0}.\)

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

Программа работы исполнителя МТ задаётся в табличном виде.

\(a_0\)\(a_1\)\(\ldots\)\(a_n\)
\(q_0\)командакоманда\(\ldots\)команда
\(q_1\)командакоманда\(\ldots\)команда
\(\ldots\)\(\ldots\)\(\ldots\)\(\ldots\)\(\ldots\)
\(q_{n-1}\)командакоманда\(\ldots\)команда

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении \(i\)-й строки и \(j\)-го столбца находится команда, которую выполняет МТ, когда головка обозревает \(j\)-й символ, находясь в \(i\)-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «\(L\)», «\(R\)», «\(N\)», «\(S\)». Символы «\(L\)» и «\(R\)» означают сдвиг в левую или правую ячейки соответственно, «\(N\)» – отсутствие сдвига, «\(S\)» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда \(0, \, L, q_3\) выполняется следующим образом: в текущую ячейку записывается символ «\(0\)», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние \(q_3.\)

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «\(Z\)», все остальные ячейки ленты заполнены пустым символом «\(\lambda\)». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «\(Z\)».

Программа

\(\lambda\)\(Z\)
\(q_0\)\(\lambda , \, L, \, q_0\)\(X, \, L, \, q_1\)
\(q_1\)\(\lambda , \, S, \, q_1\)\(X, \, L, \, q_1\)

заменяет на ленте все символы «\(Z\)» на «\(X\)» и останавливает исполнителя в первой ячейке слева от последовательности символов «\(X\)»

Возможное начальное состояние исполнителя:

\(\ldots\)\(\lambda\)\(\lambda\)\(Z\)\(Z\)\(Z\)\(Z\)\(\lambda\)\(\lambda\)\(\ldots\)
\(\blacktriangle q_0\)

Конечное состояние исполнителя после завершения выполнения программы:

\(\ldots\)\(\lambda\)\(\lambda\)\(X\)\(X\)\(X\)\(X\)\(\lambda\)\(\lambda\)\(\ldots\)
\(\blacktriangle q_0\)

Выполните задание.

На ленте в соседних ячейках записана последовательность из \(1000\) символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «\(\lambda\)». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

\(\lambda\)\(1\)\(0\)
\(q_0\)\(\lambda , \, L, \, q_1\)
\(q_1\)\(\lambda , \, S, \, q_1\)\(0, \, S, \, q_1\)\(1, \, L, \, q_1\)

После выполнения программы на ленте осталось ровно \(343\) нуля. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Если все \(1000\) непустых символов в начальной строке будут равны \(0,\) то после выполнения программы в конечной строке не останется вообще нулей. Значит, хотя бы один символ \(1\) должен присутствовать в строке. Действительно, если входная строка будет иметь вид $$\lambda \underbrace{0 \ldots 0}_{342} 1 \underbrace{0 \ldots 0}_{657} \lambda$$ на выходе получим ровно \(343\) нуля. Для проверки напишем программу

Python


#s = ['l'] + ['0'] * 1000 + ['l'] # Для такой строки в конце выпонения программы нулей совсем не останется
s = ['l'] + ['0'] * 342 + ['1'] + ['0'] * 657 + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = len(s) - 1
state='q0'
table = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,L,q1'},
         '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'R': -1, 'S': 0}
s[p], m, state = table[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = table[s[p]][state].split(',')
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: \(999\)

kege1

kege2

kege3

Новый тренажёр-эмулятор
Станции КЕГЭ

Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене

Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
​ Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
  1. 13 октября 2026 года
  2. 3 декабря 2026 года
  3. 21 января 2027 года
  4. 19 февраля 2027 года
  5. 23 марта 2027 года
  6. 27 апреля 2027 года
Математика ОГЭ 9 класс
  1. 23 сентября 2026 года
  2. 1 декабря 2026 года
  3. 22 января 2027 года
  4. 3 марта 2027 года
  5. 14 апреля 2027 года
Физика ОГЭ 9 класс
  1. 19 октября 2026 года
  2. 10 декабря 2026 года
  3. 29 января 2027 года
  4. 17 марта 2027 года
  5. 22 апреля 2027 года
Математика ЕГЭ 10 класс
  1. 3 февраля 2027 года
  2. 11 мая 2027 года
Информатика ЕГЭ 11 класс
  1. 22 октября 2026 года
  2. 15 декабря 2026 года
  3. 26 января 2027 года
  4. 2 марта 2027 года
  5. 13 апреля 2027 года
Математика ЕГЭ 11 класс
  1. 30 сентября 2026 года
  2. 17 декабря 2026 года
  3. 9 февраля 2027 года
  4. 16 марта 2027 года
  5. 21 апреля 2027 года
Физика ЕГЭ 11 класс
  1. 14 октября 2026 года
  2. 16 декабря 2026 года
  3. 4 февраля 2027 года
  4. 12 марта 2027 года
  5. 9 апреля 2027 года