Шешімі: Подсчёт нулей после работы Редактора
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Определите количество нулей в строке, получившейся в результате применения программы к входной строке $1\underbrace{00\ldots00}_{55}$, то есть к строке, состоящей из единицы, за которой следуют 55 нулей подряд.
Программа:
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 001)
ИНАЧЕ заменить (1, 00)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Шешім по шагам
5 қадамИзначально единица стоит перед 55 нулями, поэтому в строке есть цепочка $10$.
Каждое выполнение команды заменить (10, 001) увеличивает число нулей на один и перемещает единицу на одну позицию вправо.
Единица должна пройти через 55 исходных нулей. Поэтому команда заменить (10, 001) выполнится 55 раз, и число нулей станет $55+55=110$.
После этого единица окажется в конце строки, цепочки $10$ уже нет. Выполняется команда заменить (1, 00), которая удаляет единицу и добавляет два нуля.
Итоговое количество нулей равно $110+2=112$.
Где здесь ошибаются
Считать, что команда заменить (10, 001) добавляет два нуля, хотя общее число нулей увеличивается только на один.
Забыть последнее выполнение команды заменить (1, 00).
Продолжить цикл после удаления единицы из строки.