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

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

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

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

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

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

НАЧАЛО

ПОКА нашлось $(5)$ ИЛИ нашлось $(77 )$ ИЛИ нашлось $(222 )$

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

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

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

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

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

ТО заменить $(222,5)$

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке $55...55 77...77 22 ...22? ◟--◝◜-◞ ◟--◝◜--◞◟--◝◜--◞ 37 56 5$

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

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

Изначально была строка $5(37)7(56)2(5).$ Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 74.

$5(37)7(56)2(5) → 7(130)2(5)$

Второе по приоритету действие — это замена пары семерок на одну семерку. Это действие перестанет выполняться, когда количество семерок не станет 1.

$7(130)2(5) → 7(1)2(5)$

Теперь можно просчитать вручную, т.к. программа близка к завершению:

$7(1)2(5) → 7(1)5(1)2(2) → 7(3)2 (2) → 7(2)2(2) → 7(1)2(2)$

Таким образом, в конце выполнения программа будет выведено 722.

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

s = ’5’ * 37 + ’7’ * 56 + ’2’ * 5
while ’5’ in s or ’77’ in s or ’222’ in s:
    if ’5’ in s:
        s = s.replace(’5’, ’77’, 1)
    elif ’77’ in s:
        s = s.replace(’77’, ’7’, 1)
    elif ’222’ in s:
        s = s.replace(’222’, ’5’, 1)
print(s)

Ответ: 722

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