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

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

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

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

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

Задача №14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 167 идущих подряд цифр 8? В ответе запишите полученную строку.

  • НАЧАЛО
  •  ПОКА нашлось (333) ИЛИ нашлось (888)
  •  ЕСЛИ нашлось (333)
  •   ТО заменить (333, 8)
  •   ИНАЧЕ заменить (888, 3)
  •  КОНЕЦ ЕСЛИ
  •  КОНЕЦ ПОКА
  • КОНЕЦ

Решение.

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

  • Программа содержит цикл с предусловием. Условное выражение, управляющее работой цикла, имеет две составляющие, объединенные дизъюнкцией: первая – «нашлось (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 следующее:

Задача. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 167 идущих подряд цифр 3? В ответе запишите полученную строку.

  • НАЧАЛО
  •  ПОКА нашлось (333) ИЛИ нашлось (888)
  •  ЕСЛИ нашлось (333)
  •   ТО заменить (333, 8)
  •   ИНАЧЕ заменить (888, 3)
  •  КОНЕЦ ЕСЛИ
  •  КОНЕЦ ПОКА
  • КОНЕЦ

Решение.

Итак,

  • ветвь ЕСЛИ: если в строке есть подстрока 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.

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

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

Ответ. 883

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