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