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