Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды: «заменить (v, w)» — заменить первое слева вхождение цепочки v на цепочку w; «нашлось (v)» — проверить, встречается ли цепочка v в строке. Если в строке нет вхождения цепочки v, команда «заменить (v, w)» не изменяет строку.
Цикл ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ выполняется первая команда, если условие истинно, и вторая команда — если условие ложно.
Какая строка получится в результате применения программы к строке, состоящей из 91 идущей подряд цифры 1?
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ
ЕСЛИ нашлось (88888)
ТО заменить (88888, 888)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
4 қадамПока в строке есть четыре последовательные единицы, программа заменяет 1111 на 888. При делении 91 на 4 получаем 22 полные группы и остаток 3.
$$91 = 4 \cdot 22 + 3$$После этих замен образуются 22 группы 888, то есть 66 восьмёрок, а в конце остаются три единицы.
$$22 \cdot 3 = 66$$Затем программа заменяет каждое первое вхождение 88888 на 888. Каждая такая замена уменьшает количество восьмёрок на 2. Из 66 восьмёрок остаются 4, поскольку 66 = 2 \cdot 31 + 4.
$$66 - 31 \cdot 2 = 4$$Цепочка 8888 не содержит ни 1111, ни 88888, поэтому цикл завершается. К четырём восьмёркам присоединяются три оставшиеся единицы.
$$8888 + 111 = 8888111$$Где здесь ошибаются
Остановиться сразу после замен 1111 на 888 и не обработать цепочку из восьмёрок.
Считать, что после замены 1111 на 888 количество цифр увеличивается.
Заменить все вхождения 88888 одновременно, хотя команда заменяет только первое слева вхождение.