Задание №12 ЕГЭ Информатика с ответом и решением
Ответ: 163
Условие
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить(111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить(v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке, состоящей из единицы, за которой следуют 80 нулей подряд. В ответе запишите только количество нулей в получившейся строке.
НАЧАЛО
ПОКА нашлось (10) ИЛИ нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 001)
ИНАЧЕ
ЕСЛИ нашлось(1)
ТО заменить (1, 000)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Подсказки — как подойти к решению
- Сравни две ветки алгоритма: пока справа есть нули, единица съедает один нуль и добавляет слева два, а когда нули кончились, работает вложенное условие с другой заменой.
- Считать нужно именно нули, а не длину строки: единиц в конце не остаётся, поэтому к числу нулей, полученному до последнего шага, прибавляется вклад финальной замены.
Решение
Рассмотрим пример.
Возьмём исходную комбинацию 100. Далее 10 заменим на 001, получится 0010. Потом еще раз, получим 00001. И на последнем шаге 1 заменим на 000. В итоге получается 0000000.
Сделаем вывод: на каждом шаге в строчке добавляются два нуля слева от единицы и удаляется один нуль справа от неё. Число нулей удвоилось. Последним шагом единица заменяется на три нуля.
Применим этот алгоритм на комбинацию с единицей и 80 нулями. На предпоследнем шаге нули удвоятся 80 · 2 = 160, то есть будет строка из 160 нулей и одна единица. Последняя единица заменится на три нуля. Таким образом, нулей будет 160 + 3 = 163.
Ответ: 163.
Приведём другое решение на языке Python.
s = '1' + '0' * 80
while ('10' in s) or ('1' in s):
if '10' in s:
s = s.replace('10', '001', 1)
elif '1' in s:
s = s.replace('1', '000')
print(s.count('0'))
Типичные ошибки
- Учтены только нули, накопленные до последнего шага. Когда единица остаётся одна, срабатывает вложенное условие с другой заменой, и она добавляет нули ещё.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №12 по информатике