Шешімі: Преобразование строки редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочка v отсутствует, строка не изменяется. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её.
Какая строка получится в результате применения приведённой программы к строке, состоящей из 83 идущих подряд цифр 1?
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
4 қадамПока в строке есть пять единиц подряд, заменяем цепочку 11111 на 88. Из 83 единиц можно выполнить 16 таких замен, так как 83 = 16 · 5 + 3.
$$83 - 16 \cdot 5 = 3$$После 16 замен образуется жол из 32 восьмёрок и 3 единиц.
$$16 \cdot 88 + 111 = 8^{32}1^3$$Цепочка из 32 восьмёрок последовательно сокращается заменами 888 на 8. Каждая такая замена уменьшает число восьмёрок на 2, поэтому останется 2 восьмёрки.
$$32 \equiv 2 \pmod{2}$$Три единицы не заменяются, так как цепочка 11111 отсутствует. Итоговая строка состоит из двух восьмёрок и трёх единиц.
Где здесь ошибаются
Заменяют все вхождения 11111 одновременно, хотя команда заменяет только первое слева вхождение.
Забывают, что после появления восьмёрок выполняется замена 888 на 8.
Продолжают заменять единицы после того, как осталось меньше пяти единиц подряд.