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

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

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

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

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

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

НАЧАЛО

ПОКА нашлось $(7)$ ИЛИ нашлось $(33 )$ ИЛИ нашлось $(888 )$

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке $77...77 33...33 88 ...88? ◟--◝◜-◞ ◟--◝◜--◞◟--◝◜--◞ 16 1600 8$

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

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

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

$7(16)3(1600)8 (8) → 3(1632)8(8)$

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

$3 8 → 3 8 (1632)(8) (1) (8)$

Прогоним вручную по шагам программы полученную строку.

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

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

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

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

s = ’7’ * 16 + ’3’ * 1600 + ’8’ * 8
while ’7’ in s or ’33’ in s or ’888’ in s:
    if ’7’ in s:
        s = s.replace(’7’, ’33’, 1)
    elif ’33’ in s:
        s = s.replace(’33’, ’3’, 1)
    elif ’888’ in s:
        s = s.replace(’888’, ’7’, 1)
print(s)

Ответ: 388

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