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