Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда заменить(v, w) заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда нашлось(v) проверяет, встречается ли цепочка v в строке, не изменяя её.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 133 идущих подряд цифр 9?
НАЧАЛО
ПОКА нашлось(22222) ИЛИ нашлось(9999)
ЕСЛИ нашлось(22222)
ТО заменить(22222, 99)
ИНАЧЕ заменить(9999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешімін қадамдап көрсету
4 қадамВ начале цепочка $22222$ отсутствует, поэтому выполняется замена первого вхождения $9999$ на $2$. Так продолжается до тех пор, пока в строке не появится цепочка из пяти двоек.
$$9999 \to 2$$Как только появляется $22222$, условие ЕСЛИ становится истинным, поэтому выполняется замена $22222$ на $99$, а не замена $9999$ на $2$.
$$22222 \to 99$$Повторяя эти действия, учитывая, что каждый раз заменяется только первое слева вхождение, получаем последовательность преобразований до момента, когда в строке не остаётся ни $22222$, ни $9999$.
$$9999^{133} \longrightarrow 2999$$После получения строки $2999$ цепочки $22222$ и $9999$ отсутствуют, поэтому цикл завершается.
$$2999$$Где здесь ошибаются
Заменять все вхождения цепочки одновременно вместо первого слева.
Выполнять замену $9999$ на $2$, когда в строке уже есть $22222$.
Продолжать цикл после исчезновения обеих искомых цепочек.