Задание №12 ЕГЭ Информатика с ответом и решением
Ответ: 12111
Условие
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 единиц?
НАЧАЛО
ПОКА нашлось (1111)
заменить (1111, 22)
заменить (222, 1)
КОНЕЦ ПОКА
КОНЕЦ
Подсказки — как подойти к решению
- Разбирай судьбу четвёрок единиц: сначала четвёрка превращается в пару двоек, а потом тройка двоек — в одну единицу. Один проход цикла укорачивает блок единиц по-разному, поэтому считай остаток внимательно.
- Основная работа — в коротком хвосте: когда единиц останется чуть больше группы из условия, распиши последние проходы цикла по символам, иначе ошибёшься на одну единицу.
Решение
Данный алгоритм сначала заменит восемь первых единицы на четыре двойки, а затем заменит эти четыре двойки на одну единицу и двойку. То есть восемь подряд идущих единиц заменяются на строку 12. Далее ещё четыре единицы заменятся на две двойки, после чего 12221..1 заменится на 111..1. Другими словами, первые 12 единиц заменятся на 2 единицы.
Далее алгоритм заменит 8 групп по 12 единиц и останется строка из 21 единицы. После этого первые 12 единиц заменятся на две и останется последовательность из одиннадцати единиц. Далее при первом проходе цикла первые четыре единицы заменятся на 22, в строке останется еще 7 единиц, при следующем проходе цикла первые четыре единицы заменятся на 22, и в этом же проходе цикла следующей командой получившиеся четыре двойки заменятся на 12. Получится строка 12111.
Ответ: 12111.
Приведём другое решение на языке Python.
s = '1' * 101
while '1111' in s:
s = s.replace('1111', '22', 1)
s = s.replace('222', '1', 1)
print(s)
Типичные ошибки
- Проходы закончены слишком рано: цикл проверяет наличие четырёх единиц подряд, поэтому короткий хвост из единиц остаётся в строке без изменений. Пересчитай хвост.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №12 по информатике