Решение: Алгоритм работы Редактора
Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Какая строка получится в результате применения программы к строке, состоящей из 81 идущих подряд цифр 1?
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (8888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (8888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение по шагам
4 шагаВ исходной строке 81 единица. Пока остаётся цепочка 1111, программа заменяет четыре единицы на три восьмёрки.
После 19 таких замен останется 5 единиц и появится 57 восьмёрок. Ещё одна замена преобразует четыре из пяти единиц в три восьмёрки:
$$1^{81} \rightarrow 8^{60}1$$Цепочки 1111 больше нет, поэтому программа начинает заменять 8888 на 8. Каждая такая замена уменьшает число восьмёрок на 3. Из 60 восьмёрок останется 3, так как 60 кратно 3.
Итоговая строка состоит из трёх восьмёрок и одной единицы.
Где здесь ошибаются
Считать, что после замены 1111 на 888 количество цифр не изменяется.
Продолжать замену 1111 на 888 после того, как в строке осталось меньше четырёх единиц.
Забыть, что замена 8888 на 8 выполняется до исчезновения всех цепочек 8888.