Решение: Преобразование строки редактором
Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки цифр v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в текущей строке, не изменяя её. Цикл выполняется, пока его условие истинно.
1НАЧАЛО 2ПОКА нашлось (111) ИЛИ нашлось (88888) 3 ЕСЛИ нашлось (111) 4 ТО заменить (111, 88) 5 ИНАЧЕ 6 ЕСЛИ нашлось (88888) 7 ТО заменить (88888, 8) 8 КОНЕЦ ЕСЛИ 9 КОНЕЦ ЕСЛИ 10КОНЕЦ ПОКА 11КОНЕЦ
Программа применяется к строке, состоящей из 101 идущей подряд цифры 1. Найдите строку, которая получится после выполнения программы.
Решение по шагам
4 шагаПока в строке встречается $111$, выполняется замена $111 \to 88$. Из 101 единицы можно выделить 33 непересекающиеся группы по 3 цифры, поэтому останутся 2 единицы.
$$101 = 33 \cdot 3 + 2$$Каждая из 33 замен создаёт две цифры 8, поэтому после первого этапа строка содержит 66 восьмёрок и две единицы.
$$33 \cdot 2 = 66$$Затем выполняются замены $88888 \to 8$. Каждая такая замена уменьшает количество восьмёрок на 4. Из 66 восьмёрок после 16 замен останутся 2 восьмёрки.
$$66 - 16 \cdot 4 = 2$$В строке больше нет ни $111$, ни $88888$, поэтому цикл завершается. Две восьмёрки и две оставшиеся единицы образуют строку $8811$.
Где здесь ошибаются
Забывают, что команда заменяет только первое слева вхождение цепочки.
Продолжают заменять восьмёрки после того, как в строке осталось менее пяти подряд идущих восьмёрок.
Неверно считают число единиц: 101 = 33 · 3 + 2.