Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет наличие цепочки v в строке, не изменяя её. Какая строка получится в результате применения программы к строке, состоящей из 81 идущей подряд цифры 1?
Программа последовательно заменяет первое вхождение цепочки 11111 на 88, а если такой цепочки нет — первое вхождение цепочки 888 на 8. Цикл выполняется, пока встречается 11111 или 888.
Шешім по шагам
3 қадамКаждая замена 11111 → 88 уменьшает количество единиц на 5 и добавляет две цифры 8. Из 81 единицы такую замену можно выполнить 16 раз: останется 1 единица, а количество цифр 8 составит 32.
$$81 - 16 \cdot 5 = 1,\quad 16 \cdot 2 = 32$$После этого цепочка 11111 отсутствует, но есть цепочка из 32 цифр 8. Замена 888 → 8 уменьшает число цифр 8 на 2. После 15 таких замен останутся две цифры 8.
$$32 - 15 \cdot 2 = 2$$Цепочка 888 больше не встречается, поэтому цикл завершается. К двум цифрам 8 добавляется оставшаяся единица.
Где здесь ошибаются
Считать, что замена 11111 на 88 выполняется только один раз.
Продолжать замену 888 на 8 после получения двух цифр 8.
Забыть об оставшейся после первых замен единице.