Решение: Работа редактора с цепочками
Исполнитель «Редактор» получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Цикл выполняется, пока его условие истинно. Какая строка получится в результате применения программы к строке, состоящей из 81 идущей подряд цифры 1?
Программа: пока в строке встречается «1111» или «88888», если встречается «1111», заменить первое вхождение «1111» на «888», иначе заменить первое вхождение «88888» на «888».
Решение по шагам
3 шагаВ начале строки находится 81 единица. Пока встречается цепочка «1111», программа заменяет её на «888». После выполнения этих замен в строке не остаётся четырёх подряд идущих единиц.
Возникающие цепочки цифр 8 затем обрабатываются по правилу «88888» → «888». Каждая такая замена уменьшает цепочку цифр 8 на две позиции.
После завершения всех замен условие цикла становится ложным: в строке нет ни «1111», ни «88888». Получается строка из четырёх цифр 8 и одной цифры 1.
Где здесь ошибаются
Заменяют все вхождения цепочки одновременно, хотя команда заменяет только первое слева вхождение.
Продолжают замену «1111» после того, как таких вхождений уже нет.
Забывают, что при отсутствии «1111» выполняется замена «88888» на «888».