Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды. В обеих командах v и w обозначают цепочки цифр.
A) заменить (v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (222,58)
преобразует строку 45222222234 в строку 4558222234.
Если в строке нет вхождений цепочки v, то выполнение команды
заменить (v,w)
не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
означает, что последовательность команд выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 80 идущих подряд цифр 1? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (2121) ИЛИ нашлось (111)
ЕСЛИ нашлось (2121)
ТО заменить (2121, 2)
ИНАЧЕ заменить (111, 12)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Выпишем первые несколько строк, которые будут являться результатом работы исполнителя, после входа в цикл ПОКА.
| Шаг | Входная строка | нашлось(2121) | заменить(2121,2) | заменить(111,12) |
| 1 |
|
нет | – |
|
| 2 |
|
нет | – |
|
| 3 |
|
да |
|
— |
| 4 |
|
нет | – |
|
| 5 |
|
да |
|
— |
| 6 |
|
нет | – |
|
| 7 |
|
да |
|
— |
| … |
Заметим, что, начиная со второго шага цикла ПОКА, на каждом втором шаге входная строка имеет одинаковое строение. Например, рассмотрим значения входных строк на 2, 4, 6, 8, . . .шагах.
На шаге 2 строка имеет вид
Количество цифр исходной строки на каждом втором шаге цикла уменьшается на 4. Если мы разделим количество цифр в входной последовательности на втором шаге на 2, то целая честь результата деления, умноженная на 4, будет номером шага, на котором входная строка будет иметь вид 12
79/4 = 19, 75; 19 · 2 = 38.
Учитывая первую строку получаем, что на 39 шаге цикла входная строка будет иметь вид 12
Так как для числа 121 условие нашлось (2121) ИЛИ нашлось (111), входящее в цикл ПОКА, ложно, то на этом цикл оканчивает свою работу. В результате будет получена строка 121.
Ответ: 121