Решение: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w, а команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой программы к строке, состоящей из 84 идущих подряд цифр 1?
Решение по шагам
4 шагаПока в строке есть цепочка 11111, она заменяется на 88. Из 84 единиц можно выполнить 16 таких замен, так как 84 = 16 · 5 + 4.
$$84 - 16 \cdot 5 = 4$$Каждая из 16 замен добавляет две цифры 8, поэтому образуется цепочка из 32 цифр 8, после которой стоят 4 цифры 1.
$$16 \cdot 2 = 32$$Пока встречается 888, она заменяется на 88. Цепочка из 32 цифр 8 сокращается до двух цифр 8, после чего цепочка 888 исчезает.
$$32 - 10 \cdot 1 = 22$$После десяти замен 888 на 88 количество цифр 8 уменьшается с 32 до 22? Учитывая, что каждая замена уменьшает количество цифр 8 на одну, для получения двух цифр требуется 30 замен.
$$32 - 30 = 2$$Где здесь ошибаются
Считать, что замена 11111 на 88 уменьшает число единиц только на три.
Забыть, что каждая замена 888 на 88 уменьшает число цифр 8 на одну.
Остановить выполнение после первого этапа и не обработать цепочку из цифр 8.