Решение: Работа исполнителя Редактор
Исполнитель Редактор получает на вход строку цифр. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки цифр v на цепочку цифр w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Какая строка получится в результате применения программы к строке, состоящей из 99 идущих подряд цифр 9?
Программа:
НАЧАЛО
ПОКА нашлось (22222) ИЛИ нашлось (9999)
ЕСЛИ нашлось (22222)
ТО заменить (22222, 99)
ИНАЧЕ заменить (9999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение по шагам
4 шагаВ начале строки находятся 99 цифр 9. Пока встречается цепочка $9999$ и не встречается $22222$, заменяется первое вхождение $9999$ на $2$.
После появления пяти идущих подряд двоек срабатывает первая ветвь условия: цепочка $22222$ заменяется на $99$. Затем снова выполняются замены $9999$ на $2$.
Продолжаем моделирование программы, каждый раз выбирая первое слева подходящее вхождение. В конечном состоянии получается строка $229$.
В строке $229$ отсутствуют цепочки $22222$ и $9999$, поэтому условие цикла ложно и выполнение завершается.
Где здесь ошибаются
Заменять все вхождения цепочки одновременно, хотя команда заменяет только первое слева.
Не учитывать, что при наличии $22222$ выполняется первая ветвь, а не замена $9999$.
Остановить выполнение сразу после исчезновения цепочки $9999$, не проверив наличие $22222$.