Навигация по странице
О задании
Задание 24 ЕГЭ по информатике посвящено обработке символьной информации и проверяет умения составлять программы для работы с текстовыми строками.
В заданиях этого типа вам обычно предлагается текстовый файл, содержащий в себе определённую последовательность символов. Максимальная длина этой последовательности не превышает 106 символов.
От вас требуется прочитать данные из файла и написать программу, для поиска максимальной подстроки, для которой выполняются требуемые условия.
Именно по типу требуемых условий мы и будем разделять данные задания. Хотя их также можно разделить по способам решения, которые включают в себя использование регулярных выражений, метода двух указателей и метода с заменой и разделением строки.
Работе с регулярными выражениями была посвящена предыдущая статья, так что подробно останавливаться на этой теме не будем. В этой статье мы разберем 4 базовых типа заданий 24, первые два из которых будем решать только с использованием регулярных выражений.
Данная статья разделена на 4 части, в каждой из которой мы разберём по одному типу 24 заданий.
Методу с заменой и разделением строки отведём третий тип этих заданий. А в четвертом типе познакомимся с решением через метод двух указателей.
Помните, что выбранные методы – это лишь наши рекомендации. В своих решениях пользуйтесь тем, что вам кажется более удобным и надёжным. Но на реальном экзамене лучше перепроверьте полученный ответ разными методами.
Тип 1
К заданиям первого типа будем относить те, формулировки которых содержат слова «максимальное количество идущих подряд последовательностей» и не содержат более никаких уточнений.
Рассмотрим такую формулировку:
Задание 2400
«Текстовый файл состоит из символов N, O и P.
Определите максимальное количество идущих подряд последовательностей символов NPO или PNO в прилагаемом файле. Искомая последовательность должна состоять только из троек NPO, или только из троек PNO, или только из троек NPO и PNO в произвольном порядке их следования.
Для выполнения этого задания следует написать программу»
В 24 заданиях мы крайне рекомендуем сначала составить какой-нибудь небольшой пример, на котором вы сможете проверить работу вашего регулярного выражения.
Допустим, составим такую строку «NNNPOPNONPOPNOOO». В ней находятся 4 тройки символов PNO и NPO.
Теперь сформулируем регулярное выражение, по которому будем определять такие последовательности. Мы ищем группу, состоящую из символов NPO или PNO, которая повторяется 1 и более раз.
В виде регулярного выражения это будет выглядеть следующим образом:
pattern = r'(NPO|PNO)+'
Сразу отметим, что проверить составленное регулярное выражение вы можете на этом сайте.
Искать совпадения в строке будем функцией finditer(). Тогда на выходе мы будем получать итератор из match-объектов.
matches = re.finditer(pattern, data)
А найти максимальную длину match-объектов можно с помощью такого списочного включения, которое передаётся функции max:
answer = max([len(match.group()) for match in matches])
Поскольку мы хотим видеть в ответе количество последовательностей (троек NPO или PNO), то получившееся в answer количество символов необходимо будет поделить на 3:
print(answer // 3)
Передадим на вход нашей программы рассмотренную ранее строку:
data = "NNNPOPNONPOPNOOO"
pattern = r'(NPO|PNO)+'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer // 3)
В результате получаем число 4 – именно столько троек NPO и PNO, идущих подряд, мы и поместили в нашу строку.
Что же, программа готова и работает корректно. Теперь можем считать файл, приложенный к условию задания, в строку data и получить ответ на задание.
Полный код программы будет выглядеть так:
import re
with open('2400.txt') as f:
data = f.readline()
pattern = r'(NPO|PNO)+'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer // 3)
В результате получаем число 327.
Далее мы будем пользоваться этим же кодом, меняться в нём будет только название файла и само регулярное выражение.
Пример 1
Рассмотрим еще одну формулировку задания этого же типа:
Задание 2405
«Текстовый файл состоит из символов K, L, M и N. В прилагаемом файле определите максимальное количество символов в непрерывной подпоследовательности, состоящей из идущих подряд групп символов KLMN в указанном порядке, при этом в начале и в конце искомой последовательности группа символов KLMN может быть неполной.
Искомая последовательность должна содержать не менее одной полной группы символов KLMN. Например, условию задачи удовлетворяют: MNKLMNKLMNK, или NKLMNKLMNKL, или KLMNKLMNKLM и т.п.
Для выполнения этого задания следует написать программу»
Найти 1 и более групп KLMN в тексте будет несложно. Для этого достаточно такого регулярного выражения: (KLMN)+
Но теперь нужно учесть «неполноценную» последовательность символов KLMN до и после найденной подстроки. В условии нам сказано, что группа символов KLMN может быть неполной.
Отсюда делаем вывод, что перед нашей последовательностью могут находиться такие символы:
- LMN
- MN
- N
Аналогично после этой последовательности могут идти такие символы:
- KLM
- KL
- K
И таких неполных групп может быть либо одна штука, либо вовсе ни одной. То есть можем использовать квантификатор «?» после каждой неполной группы символов. Значит, можем сформировать такое регулярное выражение:
(LMN|MN|N)?(KLMN)+(KLM|KL|K)?
В целом, на этом все решение и заканчивается. Осталось только подставить это регулярное выражение в шаблон кода, который мы вывели ранее, и получить ответ:
import re
with open('2405.txt') as f:
data = f.readline()
pattern = r'(LMN|MN|N)?(KLMN)+(KLM|KL|K)?'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer)
После завершения работы программы на экране видим число 182.
Пример 2
И для закрепления решим задание с такой формулировкой:
Задание 2416
«Текстовый файл состоит из символов A, B, C, D, E.
Определите максимальное количество подряд пар символов вида гласная + согласная в прилагаемом файле.
Для выполнения этого задания следует написать программу»
Из представленных в условии букв гласными являются только две: A и E. Тогда в регулярном выражении будем требовать, чтобы сначала шла одна из гласных букв (A или E), а затем одна и более (квантификатор «+») букв B, C или D.
В итоге регулярное выражение будет таким:
pattern = r'(?:[A|E][B|C|D])+'
Подставляем его в уже известный нам шаблон кода и не забываем, что в ответ нужно дать количество пар символов, так что полученное значение нужно будет поделить на 2.
import re
with open('2416.txt', 'r') as file:
data = file.readline()
pattern = r'(?:[A|E][B|C|D])+'
matches = re.finditer(pattern, data)
answer = max([len(match.group()) for match in matches])
print(answer//2)
В результате получаем число 202, которое и будет ответом в этом задании.