Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке. Какая строка получится в результате применения программы к строке, состоящей из 81 идущей подряд цифры 1?
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (88888, 888)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
4 қадамНа первом этапе программа заменяет вхождения 1111 на 888. Из 81 единицы можно выполнить 20 таких замен, поскольку 81 = 4 · 20 + 1.
$$1^{81} \rightarrow 888^{20}1$$После этого цепочки 1111 нет, но имеется цепочка из 60 восьмёрок. Каждая замена 88888 на 888 уменьшает её длину на 2.
Замены выполняются, пока длина цепочки восьмёрок не станет меньше 5: 60 \rightarrow 58 \rightarrow \dots \rightarrow 4. Оставшаяся единица сохраняется.
Итоговая жол состоит из төрт восьмёрок и одной единицы.
Где здесь ошибаются
Забывают, что команда заменяет только первое слева вхождение цепочки.
Продолжают заменять 88888 после того, как в строке осталось меньше пяти восьмёрок.
Считают, что замена 1111 на 888 сохраняет длину строки.