Исполнитель Редактор

Умения выпускников исполнить алгоритм с фиксированным набором команд для определенного исполнителя проверяются в задаче №14 экзаменационной работы по информатике. РЕДАКТОР является одним из возможных вариантов исполнителей.

Система команд исполнителя РЕДАКТОР состоит из двух команд (в обеих командах v и w обозначают цепочки цифр):

• заменить (v, w).
  Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 011115 в строку 02715. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
• нашлось (v).
  Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Для подготовки к ЕГЭ по информатике рассмотрим типовые задания.

Решение.

Проанализируем алгоритм.

• Программа содержит цикл с предусловием. Условное выражение, управляющее работой цикла, имеет две составляющие, объединенные дизъюнкцией: первая – «нашлось (333)», вторая – «нашлось (888)». Значит, тело цикла будет выполняться, если окажется истинным хотя бы одна из них, в противном случае программа останавливается.
• Тело цикла представляет из себя полную форму условного оператора:
  • если в строке есть подстрока 333, то происходит ее замена на 8 (ветвь ЕСЛИ)
  • если в строке нет подстроки 333, но есть подстрока 888, то она заменяется на 3 (ветвь ИНАЧЕ)

Исполним формально алгоритм для исходной строки.

1. Исходная строка имеет 167 идущих подряд цифр 8 (888…8). Значит, условие выполнения тела цикла истинно (нашлось (888)).
2. Так как в исходной строке нет подстроки 333, то выполняется ветвь ИНАЧЕ и происходит замена подстроки 888 на 3. Таким образом, после одного шага цикла строка будет иметь следующий вид: 3888…8 (цифр 8 теперь 164).
3. Очевидно, после трех шагов цикла строка примет следующий вид: 333888…8 (цифр 8 теперь 158).
4. На следующем шаге при проверке условия «нашлось (333)» получаем истину, поэтому выполняется ветвь ЕСЛИ и заменяется подстрока 333 на 8 (цифр 8 теперь 159).
5. Не трудно заметить, что за 4 шага в строке девять цифр 8 заменяются на одну 8 (т. е. удаляется 8 восьмерок).
6. Выясним, сколько раз в исходной строке встретится по 8 восьмерок и какой будет строка после проведенных преобразований:
   167 ÷ 8 = 20 (остаток 7).
7. Значит, строка имеет следующий вид: 8888888.
8. В результате двух последних шагов цикла подстроки 888 заменяются на тройки и окончательно получаем строку 338.

Ответ. 338

Выясним, как изменится результат работы алгоритма, если в исходной строке вместо цифр 8 будут записаны цифры 3, т. е. теперь содержание задачи 14 следующее:

Решение.

Итак,

• ветвь ЕСЛИ: если в строке есть подстрока 333, то она заменяется на 8;
• ветвь ИНАЧЕ: если в строке нет подстроки 333, но есть подстрока 888, то происходит ее замена на 3.

Исполним формально алгоритм для исходной строки.

1. Исходная строка имеет 167 идущих подряд цифр 8 (888…8). Значит, условие выполнения тела цикла истинно (нашлось (888)).
2. В исходной строке есть подстрока 333, поэтому выполняется ветвь ЕСЛИ и происходит замена подстроки 333 на 8.
3. Подобные замены будут происходить до тех пор, пока в строке будет найдена подстрока 333. Значит, на данном этапе выполнится следующее число шагов цикла: 167 ÷ 3 = 82.
4. Один шаг цикла приводит к удалению трех цифр 3 и замене их одной цифрой 8. Поэтому после 82 шагов строка будет содержать 82 цифры 8 и будет иметь следующий вид: 888…83.

Нетрудно заметить, что теперь мы вернулись по сути к предыдущей задаче. Применим рассуждения, приведенные выше:

5. Итак, в исходной строке нет подстроки 333, поэтому выполняется ветвь ИНАЧЕ и происходит замена подстроки 888 на 3.
6. После трех шагов цикла строка примет следующий вид: 333888…83 (цифр 8 теперь 73).
7. На следующем шаге выполняется ветвь ЕСЛИ и заменяется подстрока 333 на 8 (цифр 8 теперь 74). Таким образом, за 4 шага удаляется 8 восьмерок.
8. Найдем, сколько останется восьмерок в строке: 74 ÷ 8 = 9 (остаток 2).
9. Окончательный вид строки после проведенных преобразований: 883

Ответ. 883

В задаче №14 ЕГЭ по информатике за курс средней школы встречаются следующие варианты исполнителей:

• Исполнитель Робот
• Исполнитель Чертежник