Задание 12

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды 
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

ПОКА условие
    последовательность команд
КОНЕЦ ПОКА

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

В конструкции

ЕСЛИ условие
    ТО команда1
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).

В конструкции

ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 81 идущей подряд цифры 1? В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
    ЕСЛИ нашлось (11111)
        ТО заменить (11111, 88)
        ИНАЧЕ заменить (888,8)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Теория

Задача на анализ исполнителя Редактор, который получает на вход строку цифр и преобразовывает ее по заданному алгоритму. Среди  задач этого номера встречаются задачи с известной исходной строкой - их легко решить анализом алгоритма или написав программу выполняющую приведенный алгоритм например на Python. 

Решение

Аналитический способ

Исходная строка

11111 11111  ... 11111 1 - 81 единица

Особенность работы ИЛИ - проверяется сначала первое условие, если оно истина, то второе не проверяется! Тогда первые 5 единиц поменяются на 2 восьмерки и это повторится 16 раз (81/5 = 16,2  - 16 раз по 5 единиц в исходной строке). Проверка условия каждый раз происходит с начала строки! В результате получится строка

888 888  ... 888 1 - 32 восьмерки и 1 единица

Далее, пока будут найдены 3 восьмерки, первые 3 из них заменятся на 1 восьмерку и количество восьмерок будет уменьшатся на 2, пока не достигнет двух. Обратите внимание, что последняя единица (81-я в исходной строке) останется. И итоговый результат 881.

Рекомендуется проверить алгоритм с помощью программы самостоятельно.

Программа

Ниже представлена программа на языке Python, в котором удобные средства работы со строками (операторы print отделенные пустыми строками используются для отладки и тестирования).

Ответ

881 (Время не более 10 минут)