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

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

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

2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Панцирь. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось $(54)$ ИЛИ нашлось $(27)$

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

ТО заменить $(55,2)$

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

ТО заменить $(22,7)$

КОНЕЦ ЕСЛИ

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

ТО заменить $(44,4)$

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

ТО заменить $(77,7)$

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Сколько цифр 7 получится в строке, полученной в результате применения приведённой выше программы к строке: $5◟5-.◝.◜.55◞4◟4-.◝.◜.44◞2◟2-.◝.◜.22◞ 7◟7..◝.◜77◞? 20 10 30 40$

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

Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: $A , (B)$ где A — цифра, которая находится в строке, а B — количество этих цифр.

Изначально была строка $5(20)4(10)2(30)7(40).$

Условно первый блок программы – это исчезновение пятерок, и появление на их месте 10 двоек, и четверок. Это происходит за счет замены 2 пятерок на одну двойку, т.е. произойдет 10 замен, а также 10 раз 2 четверки заменятся на 1 (9 раз сотрется четверка). Стоит заметить, что последняя четверка не сотрется, вместо нее сотрется первая попавшаяся в строке семерка. В итоге получится следующая строка:

$2(10)4(1)2(30)7(39)$

Далее все двойки, стоящие до четверки, заменятся на 7.

$2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 → 7 2 4 2 7 (10) (1) (30) (39) (1) (8)(1) (30) (38) (2) (6) (1) (30)(38) (1) (6) (1) (30) (38) (2) (4) (1)(30&#x002$

Можно заметить, что в определенный момент программа доходит до уменьшения количества двоек перед четверкой без добавления новых семерок в начале строки или удаления семерок из группы, находящейся в конце. Это будет происходить до полного удаления группы двоек перед четверкой. В результате получим следующую строку:

$7 4 2 7 (1) (1) (30)(38)$

Похожие действия произойдут с группой двоек после четверки:

$7(1)4(1)2(30)7(38) → 7(1)4(1)7 (1)2(28)7(37) → 7(1)4(1)7(2)2(26)7 (37) → 7(1)4(1)7(1)2(26)7(37)$

Как видно, после достижения отметки 28 в количестве двоек программа начинает их уменьшать, не затрагивая семерки. Таким образом после выполнения программы останется следующая строка:

$7(1)4(1)7(1)7 (37)$

Количество оставшихся семерок равно 39.

Решение программой

s = ’5’ * 20 + ’4’ * 10 + ’2’ * 30 + ’7’ * 40

while ’54’ in s or ’27’ in s:
    if ’55’ in s:
        s = s.replace(’55’, ’2’, 1)
    elif ’22’ in s:
        s = s.replace(’22’, ’7’, 1)
    if ’44’ in s:
        s = s.replace(’44’, ’4’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’7’, 1)

count_of_sevens = s.count(’7’)
print(count_of_sevens)

Ответ: 39

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