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