Задача к ЕГЭ по информатике на тему «исполнитель «редактор»

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в которых $v$ и $w$ обозначают последовательности цифр:

А) $заменить (v,w ).$

Эта команда заменяет в строке первое слева вхождение последовательности $v$ на последовательность $w.$

Например, выполнение команды заменить $(333,3)$ преобразует строку $1333572$ в строку $13572.$

Если в строке нет вхождений последовательности $v,$ то выполнение команды заменить $(v,w)$ не меняет эту строку.

Б) $Наш лось (v).$

Эта команда проверяет, встречается ли последовательность $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение $« истин а»$ , в противном случае возвращает значение $«лож ь»$ .

Строка исполнителя при этом не изменяется.

Цикл

$П ОК А усл овие$

$посл едовательность ком анд$

$К ОН ЕЦ ПО КА$

Выполняется, пока условие истинно.

Какая строка получится в результате применения приведённой ниже программы к строке: $1...12 ...2333? ◟-◝1◜0 ◞◟-◝5◜ ◞$

$Н АЧА ЛО$

$П ОК А нашлось(12) И ЛИ наш лось(13) ИЛИ нашлось(33333)$

$ЕС ЛИ наш лось(23)$

$ТО заменить(23,3)$

$И НАЧ Е ЕСЛ И наш лось(13)$

$ТО заменить(13,33)$

$И НАЧ Е ЕСЛ И наш лось(333)$

$ТО заменить(333,3)$

$К ОН ЕЦ ЕС ЛИ$

$К ОН ЕЦ ПО КА$

$К ОНЕ Ц$

Если вы получили строку вида $111222111$ , то в ответе нужно записать $1(3)2(3)1(3)$ , а для строки $11222$ — $112(3)$ , скобки ставятся при трех и более повторениях.

Решение ручками:

Начнем работу нашего алгоритма. Так как в исходной строке мы нашли $23$ , то заменим $23$ на $3$ .

Получим строку $1 ...1 2...2 333 ◟-◝1◜0 ◞ ◟ ◝◜4 ◞$

На данной итерации цикла строка больше меняться не будет, идем дальше. Вновь встречаем $23$ , можем заметить, что если встречается $23$ , то количество $2$ уменьшается на один, а количество $3$ остается неизменным, тогда можем выполнить эти дейстия еще четыре раза, пока у нас не закончатся $2$ .

Получим строку $1◟-.◝..◜1 ◞ 333 10$

Так как у нас уже нет комбинаций $23$ , проверяем следующие условия: находим $13$ — заходим в цикл. Под первое условие наша строка не подходит — у нас нет $23$ , но зато она подходит под второе, ведь у нас есть $13$ . Тогда заменим $13$ на $33$ .

Получим строку $1◟-.◝..◜1 ◞ 333 9$

Заметим, что количество $1$ уменьшается на один, а количество $3$ увеличивается на $1$ . Тогда повторим данное действие, пока у нас есть комбинации $13$ , а именно еще девять раз. Получим строку $3◟-..◝.◜3 ◞ 13$ . Теперь мы будем заходить только в третье условие. Заметим, что на каждой итерации кол-во троек уменьшается на $2$ . Значит в какой-то момент мы дойдём до строки $3◟. ◝.◜.3 ◞ 5$ . После этого в последний раз зайдём в третье условие и получим строку $3◟-.◝..◜3 ◞ 3$ , то есть запишем в ответ $3(3)$ .

Решение прогой:

s = ’1’ * 10 + ’2’ * 5 + ’333’
while ’12’ in s or ’13’ in s or ’33333’ in s:
    if ’23’ in s:
        s = s.replace(’23’, ’3’, 1)
    elif ’13’ in s:
        s = s.replace(’13’, ’33’, 1)
    elif ’333’ in s:
        s = s.replace(’333’, ’3’, 1)
print(s)

Ответ: 3(3)

Задача к ЕГЭ по информатике на тему «исполнитель «редактор» – известная строка» №8