Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразует её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет наличие цепочки v, не изменяя строку. Цикл выполняется, пока условие истинно.
Какая строка получится в результате применения программы к строке, состоящей из 92 идущих подряд цифр 3?
НАЧАЛО
ПОКА нашлось (999) или нашлось (333)
ЕСЛИ нашлось (999)
ТО заменить (999, 3)
ИНАЧЕ заменить (333, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
4 қадамВ начале в строке нет цепочки 999, поэтому программа заменяет первое вхождение 333 на 9. Из 92 цифр 3 образуются 30 цифр 9 и 2 цифры 3.
$$92 = 30 \cdot 3 + 2$$Пока в строке есть 999, программа заменяет первое такое вхождение на 3. Десять таких замен уничтожают 30 цифр 9 и добавляют 10 цифр 3 к двум оставшимся, поэтому получается 12 цифр 3.
$$30 \to 0,\quad 2+10=12$$Из 12 цифр 3 три замены 333 на 9 дают строку из трёх цифр 9 и трёх цифр 3. Так как появилось 999, оно заменяется на 3, и получается 4 цифры 3.
$$3^ {12} \to 9^3 3^3 \to 3^4$$Одна замена 333 на 9 из четырёх цифр 3 даёт строку 93. В ней нет ни 999, ни 333, поэтому цикл завершается.
$$3^4 \to 93$$Где здесь ошибаются
Продолжают заменять 333 на 9, не учитывая, что при появлении 999 приоритет имеет первая ветвь условия.
Считают, что после получения четырёх цифр 3 нужно сразу выполнить ещё одну замену 333, не отслеживая порядок символов.