Разбор 14 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 6 минут.
Проверяемые элементы содержания: умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд.
Элементы содержания, проверяемые на ЕГЭ: Вычислимость. Эквивалентность алгоритмических моделей.
Задание 14
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды
заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (3333) ИЛИ нашлось (8888)
ЕСЛИ нашлось (3333)
ТО заменить (3333, 88)
ИНАЧЕ заменить (8888, 33)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Ответ: ________
Разбор 14 задания ЕГЭ 2017
Программа будет работать до тех пор, пока в строке есть цепочка цифр 3333 или цепочка цифр 8888.
Если в строке встречается 3333, то заменяем на 88.
Если в строке нет цепочки 3333, но встречается цепочка 8888, то заменяем ее на 33.
Наша строка состоит из 69 идущих подряд цифр 8.
1) меняем первые 8888 на 33 и получаем
33 и (65 цифр 8)
2) меняем следующие 8888 на 33 и получаем
3333 и (61 цифру 8)
3) теперь у нас появилась цепочка 3333, поэтому мы должны заменить ее на 88
получаем строку состоящую из 63 цифр 8
Анализируем что произошло!
А получилось следующее, за 3 шага мы заменили 8 восьмерок на 2 (или удалили 6 восьмерок из нашей строки).
Становится понятно, что за каждые 3 шага мы будем удалять по 6 восьмерок.
63-6=57
57-6=51
51-6=45
45-6=39
39-6=33
33-6=27
27-6=21
21-6=15
15-6=9
9-6=3 останется строка состоящая из 3 идущих подряд 8 (888)
Ответ: 888