Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (222)
заменить (111, 22)
заменить (222, 11)
заменить (11, 2)
заменить (22, 1)
КОНЕЦ ПОКА
КОНЕЦ
Определите, сколько различных строк может получиться в результате применения этой программы к строкам, состоящим только из единиц.
Приведём решение на языке Python.
otv = []
for i in range(1,1000):
s = '1' * i
while ('111' in s) or ('222' in s):
s = s.replace('111', '22', 1)
s = s.replace('222', '11', 1)
s = s.replace('11', '2', 1)
s = s.replace('22', '1', 1)
otv.append(s)
print(len(set(otv)))
Ответ: 8.