Шешімі: Преобразование строки Редактором
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Если в строке нет вхождений цепочки v, строка не изменяется. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её.
Цикл выполняется, пока условие истинно. В конструкции «ЕСЛИ условие ТО команда ИНАЧЕ команда КОНЕЦ ЕСЛИ» выполняется первая команда, если условие истинно, и вторая — если условие ложно.
Определите количество нулей в строке, получившейся в результате применения программы к входной строке, состоящей из единицы, за которой следуют 90 нулей подряд.
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 0001)
ИНАЧЕ заменить (1, 000)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
4 қадамВ начале жол имеет вид $10^{90}$: одна единица и 90 нулей справа от неё.
Пока после единицы есть ноль, выполняется замена $10 \to 0001$. Единица перемещается на две позиции вправо, а общее количество нулей увеличивается на 2.
После 90 таких замен единица окажется в конце строки. За это время количество нулей увеличится на $90 \cdot 2 = 180$ и станет равным $90 + 180 = 270$.
Когда после единицы уже нет нуля, выполняется замена $1 \to 000$. Она добавляет ещё 3 нуля и удаляет единицу.
Где здесь ошибаются
Считать, что замена $10 \to 0001$ добавляет три нуля, не учитывая удаление исходного нуля.
Забыть последнюю замену $1 \to 000$.
Остановить процесс раньше, чем единица дойдёт до конца строки.