Информатика. ЕГЭ
Задание 12. Информатика. ЕГЭ. Поляков-8271
- Просмотры: 1016
- Изменено: 24 сентября 2025
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из \(1000\) символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «\(\lambda\)». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.
Программа работы исполнителя:
| \(\lambda\) | \(0\) | \(1\) | |
| \(q_0\) | \(\lambda , \, R, \, q_1\) | ||
| \(q_1\) | \(\lambda , \, S, \, q_1\) | \(1, \, R, \, q_2\) | \(0, \, R, \, q_2\) |
| \(q_2\) | \(\lambda , \, S, \, q_2\) | \(0, \, S, \, q_2\) | \(1, \, R, \, q_1\) |
Команды движения каретки: \(L\) – влево, \(R\) – вправо, \(S\) – стоп. После выполнения программы на ленте осталось одинаковое количество нулей и единиц. Определите минимально возможное количество единиц, которое могло быть в исходной последовательности.
Решение:
Найдет максимальное количество нулей, которое может быть размещено в строке. Пусть на нулевой позиции стоит пустой символ. При переходе к первой позиции исполнитель переходит в состояние \(q_1.\) Замечаем, что если в строке встретятся два подряд идущих нуля, то исполнитель закончит работу либо на первом нуле (если уже находится в состоянии \(q_1),\) либо на втором нуле. Чтобы добавить как можно больше нулей, мы должны их размешать в парах \(01,\) причём каждая такая пара перейдет в пару из двух единиц \(11.\) Ясно, что таких пар не может быть больше, чем \(250.\) Точнее, их будет ровно \(249.\) Они дадут \(498\) единиц. Далее размещаем на \(499\) и \(500\) позиции нули. Исполнитель, на \(499\) шаге, находясь в состоянии \(q_1\) заменит \(0\) на \(1\) и остановится на \(500\)-м шаге. Оставшиеся \(500\) позиций мы должны заполнить нулями, за исключением одной позиции. Номер позиции, где может стоять \(1\) любой из диапазона \([501:1000].\) Т.о., максимум нулей, которое мы можем разместить в исходной строке, равно \(750.\) Значит, минимум единиц, которое может встретиться в строке, будет \(1000 - 750 = 250.\)
Программный тест:
Python
mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
'0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
'1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
s = ['l'] + list('01' * 249) + ['0'] * 501 + ['1'] + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
p += step[act[1]]
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')
Ответ: \(250\)
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года