Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w)
нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение "истина", в противном случае возвращает значение "ложь".
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2119 двоек)?
Обозначим через m количество единиц, а через n - количество двоек.
В цикле m и n изменяются следующим образом:
n=n-3
m=m+1
m=m-3
n=n+1
Итого: m=m-2; n=n-2. То есть и m и n уменьшаются на 2.
m и n - нечетные, n-m=100. Следовательно, через некое количество вычислений, последовательно уменьшаясь на 2, m примет значение 3, а n - значение 103.
n=n-3=103-3=100
m=m+1=3+1=4
m=m-3=4-3=1
n=n+1=100+1=101
Теперь цепочки их трех единиц нет. До тех пор, пока цепочка из трех единиц не образуется, операции m=m-3 и n=n+1 мы, по условию, не производим. Повторим несколько вычислений в цикле.
n=n-3=101-3=98
m=m+1=1+1=2
возвращаемся к началу цикла
n=n-3=98-3=95
m=m+1=2+1=3
m=m-3=3-3=0
n=n+1=95+1=96
возвращаемся к началу цикла
n=n-3=96-3=93
m=m+1=0+1=1
Значения m=1 и n=101 изменились на m=1 и n=93.
То есть m как было, так и осталось равным единице, а n уменьшилось на 8.
8*[101/8]=8*12=96
101-96=5
То есть, через некоторое количество вычислений, мы придем к следующим значениям: m=1 и n=5
Далее получаем:
n=n-3=5-3=2
m=m+1=1+1=2
Поскольку строка из трех двоек больше не находится, цикл завершается.
На выходе получаем строку из двух единиц и двух двоек.