Решение: Преобразование строки цифр
Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке. Цикл выполняется, пока его условие истинно.
Какая строка получится в результате применения программы к строке, состоящей из 132 идущих подряд цифр 9?
НАЧАЛО
ПОКА нашлось (22222) ИЛИ нашлось (9999)
ЕСЛИ нашлось (22222)
ТО заменить (22222, 99)
ИНАЧЕ заменить (9999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение по шагам
4 шагаПока в строке нет пяти цифр 2 подряд, выполняется замена первого фрагмента $9999$ на $2$. Для достаточно длинной последовательности из девяток пять таких замен дают $22222$.
$$9999 \to 2$$Когда появляется фрагмент $22222$, он заменяется на $99$. Поэтому после полного цикла количество девяток уменьшается на 18: четыре заменённых блока содержат 20 девяток, а результат добавляет 2 девятки.
$$n \to n - 20 + 2 = n - 18$$Последовательность количеств девяток после циклов: $132 \to 114 \to 96 \to 78 \to 60 \to 42 \to 24 \to 6$.
Из шести девяток первая замена даёт строку $299$. В ней нет ни $9999$, ни $22222$, поэтому цикл завершается.
$$999999 \to 299$$Где здесь ошибаются
Продолжают замену после исчезновения фрагментов $9999$ и $22222$.
Считают, что команда «заменить» заменяет все вхождения сразу, а не первое слева.
Забывают, что при наличии $22222$ выполняется именно эта ветвь условия.