cEyy6NEbWEBq5IrK7X6Mm 129097fad7b548c89cb64cacb6e9275c scaled

Задание 12 ЕГЭ по информатике нацелено на проверку умений учащихся составлять и анализировать алгоритм для конкретного исполнителя с фиксированным набором команд.

На данный момент существует 3 типа исполнителей в данном задании: Редактор, Чертёжник и Робот. В данной статье мы рассмотрим работу лишь одного из них — Редактора.

Но не стоит беспокоиться насчет других исполнителей. На ЕГЭ обычно используют именно формулировки данного задания, в которых представлен исполнитель Редактор. Формулировки задания 12 с двумя другими исполнителями являются авторскими и не используются на реальном экзамене.

Для решения данного задания вам необходимо представить написанный в условии алгоритм на используемом вами языке программирования, сформировать входные данные и вывести на экран результат работы алгоритма.

Входными данными в этом задании являются строки, составленные из определённого количества букв или цифр. Передавая эту строку алгоритму, мы производим замену определённых символов до тех пор, пока выполняется заданное условие.

Результатом работы алгоритма будет новая строка. В ответ мы даём либо саму строку, либо количество символов в ней. Но также может потребоваться провести еще некоторые вычисления перед тем, как дать ответ на задание.

В итоге, можно сказать, что для успешного решения задания 12 вам необходимо знать, как составляются алгоритмы, как верно написать представленные в условии команды на языке программирования и как использовать доступные в языке программирования методы обработки строк.

Типы алгоритмов

В мире программирования алгоритмы играют роль своеобразных рецептов, по которым компьютер «готовит» решение задачи. Алгоритм можно представить как подробную инструкцию, которая говорит исполнителю – будь то человек, компьютер или даже робот – что именно нужно делать на каждом этапе решения задачи.

Природа алгоритмов удивительно разнообразна. Простейшие из них – линейные алгоритмы – напоминают прямую дорогу, где каждое действие следует за предыдущим без каких-либо отклонений.

Примером такого алгоритма может служить ваша стандартная утренняя рутина:

  1. Подъем в 6 утра
  2. Разглаживание простыней утюгом
  3. Пробежка 3 километра в парке
  4. Приём ледяной ванны
  5. Завтрак из авокадо и красной рыбы

Такие алгоритмы выполняются последовательно друг за другом, без пропуска какого-либо действия. Согласитесь, вы же не сможете пойти на пробежку, не разгладив простыни, не так ли?

Если же без иронии, то у нас может быть определённый линейный алгоритм преобразования одного числа в другое, например:

  1. Добавить 5
  2. Умножить на 2
  3. Отнять 7
Задание 12 1

Если данному алгоритму на вход передать число 6, то получим следующую последовательность математических операций:

6 + 5 = 11

11 * 2 = 22

22 – 7 = 15

Число 15 и будет итого работы данного линейного алгоритма.

Более сложные – разветвляющиеся алгоритмы – похожи на перекрёстки, где программа выбирает дальнейший путь на основе определённых условий.

Соответственно, такие алгоритмы содержат в себе блок с условной конструкцией. Давайте составим условную конструкцию, которая проверяет уровень доступа к контенту согласно возрасту:

ЕСЛИ (возраст >= 18)
   ТО верни "Доступ разрешен"
ИНАЧЕ ЕСЛИ (возраст >= 16)
    ТО верни "Требуется согласие родителей"
ИНАЧЕ верни "Доступ запрещен"
Задание 12 2

Особый интерес представляют циклические алгоритмы, которые позволяют многократно повторять определённые действия. Представьте, что вам нужно перебрать колоду карт в поисках всех тузов – это классический пример задачи, требующей циклического алгоритма.

При этом важно помнить, что любой цикл должен иметь условие завершения, иначе программа может попасть в бесконечный круговорот действий, называемый зацикливанием.

Структура циклического алгоритма напоминает механизм часов. Подобно тому, как часы имеют начальное положение стрелок, шаг движения и условие полного оборота, циклический алгоритм включает три ключевых элемента:

  1. Подготовка цикла – установка начальных значений и определение условий работы
  2. Тело цикла – набор повторяющихся действий
  3. Управление циклом – проверка условий для продолжения или завершения работы

При этом циклические алгоритмы также делятся на несколько подтипов:

  1. Циклы с предусловием
  2. Циклы с постусловием
  3. Вложенные циклы
  4. Циклы с счётчиком

В циклах с предусловием мы сначала проверяем, выполняется ли условие, написанное в начале цикла. Если оно выполняется, то есть истинно, то переходим к исполнению команд, написанных в теле цикла.

Это продолжается до тех пор, пока условие не станет ложным. Тогда цикл и завершит свою работу.

Примером алгоритма, содержащего в себе цикл с предусловием, может быть алгоритм поиска ключей в комнате:

ПОКА ключи не найдены:
    Выбрать следующее место для осмотра
    Осмотреть выбранное место
    Отметить место как проверенное
Задание 12 3

Цикл с постусловием (или цикл с последующей проверкой условия) — это цикл, в котором тело цикла выполняется перед проверкой условия. Это означает, что тело цикла выполняется хотя бы один раз, независимо от того, истинно ли условие.

Представьте себе процесс оплаты товаров в магазине. Покупатель подходит к кассе с корзиной товаров, и кассир начинает сканировать товары.

После сканирования каждого товара кассир проверяет, есть ли еще товары в корзине. Если товары есть, кассир продолжает сканировать. Если товаров нет, процесс сканирования товаров завершается.

Что будет происходить в таком цикле с точки зрения программирования:

  1. Начало процесса: покупатель подходит к кассе с корзиной товаров. Это аналогично началу цикла с постусловием, где тело цикла выполняется перед проверкой условия.
  2. Сканирование товара: кассир сканирует товар. Это аналогично выполнению тела цикла.
  3. Проверка условия: кассир проверяет, есть ли еще товары в корзине. Это действие аналогично проверке условия в конце цикла с постусловием.
    • Если товары есть, кассир продолжает сканировать следующий товар. Это аналогично повторному выполнению тела цикла, если условие истинно.
    • Если товаров нет, процесс сканирования завершается. Это аналогично завершению цикла, если условие ложно.

Теперь перейдём ко вложенным циклам. Вложенный цикл — это цикл, который находится внутри другого цикла. Вложенные циклы часто используются для выполнения задач, требующих двойной итерации, например, обхода двумерного массива или выполнения действий для каждой пары элементов из двух наборов данных.

Представьте себе кинотеатр с несколькими рядами и местами в каждом ряду. Менеджер кинотеатра хочет проверить, есть ли свободные места для группы зрителей, которая хочет сесть вместе. Для этого менеджер проверяет каждый ряд и каждое место в этом ряду, чтобы найти подходящие места.

И теперь рассмотрим, как будет выглядеть эти действия с точки зрения программирования:

  1. Начало процесса: менеджер начинает с первого ряда. Это аналогично началу внешнего цикла.
  2. Проверка ряда: менеджер проверяет каждое место в текущем ряду. Это аналогично внутреннему циклу, который проходит по каждому месту в ряду.
    • Если находит достаточное количество свободных мест подряд, процесс завершается успешно. Это аналогично завершению внутреннего цикла при нахождении нужного условия.
    • Если не находит, переходит к следующему ряду. Это аналогично переходу к следующей итерации внешнего цикла.
  3. Повторение для всех рядов: менеджер повторяет процесс для всех рядов, пока не найдет подходящие места или не проверит все ряды. Это аналогично повторению внешнего цикла до завершения всех итераций.

Циклы со счётчиком используются в тех случаях, когда заранее известно необходимое количество повторений алгоритма (итераций).

Например, при подготовке к ЕГЭ по информатике вам необходимо научиться решать 27 заданий. И для каждого задания существует определённый порядок подготовки:

  1. Прочитать статью по этому заданию
  2. Разобрать примеры из этой статьи
  3. Самостоятельно решить несколько примеров этого задания

Эти действия и будут составлять тело цикла. В моменте подготовки цикла мы определяем количество необходимых итераций и специальную переменную-счётчик, которая будет в себе хранить количество выполненных операций цикла.

На этапе управления циклом будет происходить увеличение значения переменной-счётчика и проверка, не превышает ли это значение заданной величины. Если значение этой переменной достигнет заданного, то цикл прекратит свою работу.

Команды Редактора

В заданиях 12 ЕГЭ по информатике команды исполнителя записаны на алгоритмическом языке. Для начала давайте поставим в соответствие каждой команде исполнителя оператор или метод языка Python. А потом уже подробно разберем каждый из них.

Обычно, первое, что вы видите в программе для Редактора, будет команда ПОКА. Она означает начало обычного циклического алгоритма (с предусловием). Этой команде соответствует оператор цикла while в Python (while с английского — «пока»).

Поскольку это у нас цикл с предусловием, то в той же строке, что и слово ПОКА будут находится и слова «нашлось». Команда «нашлось» означает, что в рассматриваемой в данной итерации цикла строке есть искомая подстрока.

Например, если мы рассматриваем подстроку «1703», то команда «нашлось(17)» вернёт истинное значение, а команда «нашлось(11)» — ложное.

В Python такую команду можно реализовать с помощью оператора проверки вхождения in. Данный код также будет проверять вхождение подстрок «17» и «11» в строку «1703»:

my_string = "1703"

print("17" in my_string)
print("11" in my_string)

Таких условий в цикле может быть несколько и объединяются они с помощью логических операторов. Чаще всего в 12 заданиях используется оператор дизъюнкции — ИЛИ. В Python дизъюнкция реализуется с помощью оператора or.

Если же мы имеем несколько условий в цикле, то, следовательно, под каждое условие необходимо выполнить определённое действие. В программе для исполнителя Редактор используются условные конструкции ЕСЛИ … ТО или ЕСЛИ … ТО … ИНАЧЕ.

В качестве условной конструкции в языке Python используется оператор if. Если же требуется реализовать конструкцию со словом ИНАЧЕ, то используется еще и оператор else.

И далее следует последняя рассматриваемая команда Исполнителя — «заменить». Она имеет два параметра, обычно обозначаемых как v и w. Суть этой в команды в том, чтобы в рассматриваемой строке заменить подстроку v на w.

В Python для замены одной подстроки на другую используется метод replace(). Причем, в случаях, когда код исполнителя содержит только оператор ЕСЛИ…ТО, можно писать этот метод без условной конструкции if. Если же присутствует еще и оператор ИНАЧЕ, то используется конструкция if…else.

Чтобы лучше разобраться в последних рассмотренных командах давайте рассмотрим такой код для исполнителя:

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

Здесь идет цикличная проверка вхождения в рассматриваемую строку подстрок 11111 или 888. Если найдена подстрока 11111, то заменяем её на 88. В противном же случае, если подстрока 11111 не найдена, но цикл еще не завершён, заменяем подстроку 888 на 8.

Давайте перепишем этот код на языке Python (исходную строку обозначим за s):

while '11111' in s or '888' in s:
    if '11111' in s:
        s = s.replace('11111', '88', 1)
    else:
        s = s.replace('888', '8', 1)

Теперь же приведём таблицу соответствия команд исполнителя операторам Python:

Команда исполнителя Соответствие в Python
ПОКА while
нашлось in
НЕ нашлось not in
ИЛИ or
ЕСЛИ…ТО… ИНАЧЕ if...else
заменить replace

Алгоритм решения задания 12

Написание программы для решения 12 задания состоит из трех основных этапов:

  1. Формирование исходной строки
  2. Реализация алгоритма программы для исполнителя на языке Python
  3. Определение условия для верного ответа

Давайте подробнее разберем каждый из этих этапов. Для начала вам необходимо сформировать строку, с которой вы будете работать в дальнейшем. Обычно она задаётся конце задания в текстовом виде, например так: «строка, состоящая из 134 идущих подряд цифр 9».

Обычно это не вызывает никаких трудностей, нам достаточно определить переменную и присвоить ей значение нужного символа, умноженное на заданное количество.

Так, для условия выше строка будет формировать следующим образом:

s = "9" * 134

Во втором этапе нам требуется переписать представленный в условии алгоритм на языке Python. Как это делается и какие операторы и методы Python соответствуют командам исполнителя мы уже рассмотрели ранее.

Далее идёт самый трудный этап — определить значение, которое будем давать в ответ. В самом простом варианте от нас могут потребовать дать в ответ строку, полученную в результате работы алгоритма. В таком случае, после завершения работы цикла выводим на экран значение переменной, в которой содержится наша строка.

Но бывают и другие формулировки, например такая: «Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 15».

Полное условие данного задания звучит так:

«Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:

НАЧАЛО
    ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
       ЕСЛИ нашлось (12)
           ТО заменить (12, 2)
       КОНЕЦ ЕСЛИ
       ЕСЛИ нашлось (322)
           ТО заменить (322, 21)
       КОНЕЦ ЕСЛИ
       ЕСЛИ нашлось (222)
           ТО заменить (222, 3)
       КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «2» (3 < n < 10 000).
Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 15

В таком случае, необходимо цикл while поместить внутри цикла со счетчиком for, в котором мы и будем перебирать все возможные значения n. А после выполнения цикла while будем проверять сумму цифр в получившейся строке и сравнивать её с 15.

Если в таком условии получим истину, то даём в ответ текущее значение n. Если получаем в условии ложь, то увеличиваем значение n и цикл while заново проводит все необходимые замены.

Решение данного задания будет следующим:

# Перебираем все n
# 3 < n 10 000
for n in range(4, 10000):
    # Формируем строку
    s = "1" + "2" * n
    # Программа Редактора
    while "12" in s or "322" in s or "222" in s:
        s = s.replace("12", "2", 1)
        s = s.replace("322", "21", 1)
        s = s.replace("222", "3", 1)
    # Ищем сумму цифр в строке
    sm = sum(int(d) for d in s)
    # Если сумма равна 15
    if sm == 15:
        # Выводим n
        print(n)
        # Завершаем работу for
        break

Пример 1

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

Дана программа для Редактора:

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

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

Здесь действуем по уже расписанному в начале алгоритму: формируем строку из ста девяток, переписываем алгоритм и после завершения работы цикла выводим полученную строку.

s = "9" * 100

while "33333" in s or "999" in s:
    if "33333" in s:
        s = s.replace("33333", "99", 1)
    else:
        s = s.replace("999", "3", 1)

print(s)

Получаем ответ — 333

Пример 2

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

  1. заменить (v, w)
  2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
  ЕСЛИ нашлось (12)
    ТО заменить (12, 2)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (322)
    ТО заменить (322, 21)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (222)
    ТО заменить (222, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», за которой следуют n цифр «2» (3 < n < 1000). Определите наибольшую длину строки, которая может быть результатом выполнения программы.

Программа для исполнителя здесь аналогична той, которую мы рассматривали ранее. Но главное отличие здесь в величине, которую необходимо дать в ответ. Здесь нужно найти наибольшую длину строки, которая получается после работы алгоритма Редактора.

Для поиска максимальной длины можем использовать стандартную конструкцию:

max_len = -float("inf")
    if len(s) > max_len:
        max_len = len(s)

Здесь мы инициализируем переменную max_len и присваиваем ей значение минус бесконечность (для поиска минимального мы бы присваивали плюс бесконечность). Далее проверяем длину строки s, если она больше текущего значения max_len, то записываем в переменную max_len значение длины строки.

Естественно, условие должно находиться внутри цикла, а объявление переменной — до цикла.

В остальном же, решение этого задание будет аналогично уже рассмотренному ранее.

max_len = -float("inf")

for n in range(4, 1000):
    s = "1" + "2" * n

    while "12" in s or "322" in s or "222" in s:
        s = s.replace("12", "2", 1)
        s = s.replace("322", "21", 1)
        s = s.replace("222", "3", 1)

    # Поиск максимальной длины
    if len(s) > max_len:
        max_len = len(s)

print(max_len)

В ответ записываем число 9

Пример 3

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (52) ИЛИ нашлось (2222) ИЛИ нашлось (1122)
   ЕСЛИ нашлось (52)
     ТО заменить (52, 11)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (2222)
     ТО заменить (2222, 5)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (1122)
     ТО заменить (1122, 25)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ 

На вход приведённой выше программе поступает строка, начинающаяся с цифры «5», а затем содержащая n цифр «2» (3 < n < 10 000).

Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, оканчивается на 7.

В данном задании все также в цикле for формируем строку, переписываем алгоритм из условия и находим сумму цифр в строке через списочное выражение:

sm = sum(int(d) for d in s)

Но здесь нам необходимо установить, что эта сумма оканчивается на 7. Сделать это можно двумя способами:

  1. Перевести сумму в строку и взять последний элемент строки, сравнив его с символом «7»:
    if str(sm)[-1]== "7":
        print(n)
        break
  1. Взять остаток от деления суммы на 10 и сравнить его с числом 7:
    if sm % 10 == 7:
        print(n)
        break

Полный код решения данного задания следующий:

for n in range(4, 10000):
    s = "5" + "2" * n

    while "52" in s or "2222" in s or "1122" in s:
        s = s.replace("52", "11", 1)
        s = s.replace("2222", "5", 1)
        s = s.replace("1122", "25", 1)

    # Ищем сумму цифр в строке
    sm = sum(int(d) for d in s)

    # Поиск максимальной длины
    if str(sm)[-1]== "7":
        print(n)
        break

В результате работы программы получаем ответ — 5.