О задании
Задание 24 ЕГЭ по информатике посвящено обработке символьной информации. Оно проверяет ваше умение составлять программы для работы с текстовыми строками — одному из важнейших навыков в программировании.
В заданиях этого типа вам предлагается текстовый файл, содержащий последовательность символов. Длина этой последовательности может достигать миллиона символов, поэтому ручной анализ исключён — без программы здесь не обойтись.
Суть задания обычно сводится к следующему: нужно прочитать данные из файла и найти подстроку максимальной длины, удовлетворяющую определённым условиям. Эти условия могут быть самыми разными: от поиска повторяющихся символов до анализа арифметических выражений.
Способы решения
Первым делом здесь стоит отметить обилие способов решения 24 заданий. Чаще всего встречаются три самых эффективных:
- Регулярные выражения
- Метод двух указателей
- Метод замены (replace) и разделения строки (split)
Регулярные выражения обычно используются для поиска подстроки в тексте по определённому шаблоны. Они позволяют описать шаблон такой подстроки буквально в одну строку кода. Но есть одна особенность: регулярные выражения используют собственный синтаксис. Так что для уверенного использования этого метода вам сначала нужно выучить, как представляются разные символы в регулярных выражениях, как работают проверки разного типа и как использовать квантификаторы.
Особенно удобны регулярные выражения, когда нужно найти последовательности одинаковых символов или подстроки определённой структуры. Главное преимущество — компактность и выразительность кода. Правда, за компактностью порой кроются проблемы как в читаемости шаблонов, так и в их составлении.
Регулярные выражения в Python мы рассматривали здесь:
Метод замены и разделения строки основан на простой идее: сначала мы преобразуем исходную строку, заменяя или удаляя ненужные символы, а затем разбиваем её на части. После этого остаётся только найти самую длинную часть. Этот метод интуитивно понятен и не требует знания специального синтаксиса.
Решать 24 задания таким способом довольно просто, нет необходимости заучивать какой-то новый синтаксис. Но зачастую такие решения не самые эффективные по скорости выполнения. А также есть ряд заданий, которые либо вовсе не решаются таким методом, либо решаются крайне сложно.
Метод двух указателей использует два индекса, которые движутся по строке и отмечают начало и конец текущей подстроки. Этот подход особенно полезен для задач, где нужно подсчитывать количество определённых символов внутри подстроки. Он работает быстро даже на очень длинных строках.
Такой метод идеально подходит для одного из типов 24 заданий. И в целом полезно будет научиться им пользоваться, если вы хотите в будущем связать свою карьеру с программированием. Те же регулярные выражения редко спрашивают на собеседованиях. А вот навыки решения задач, в которых следует применить метод двух указателей, зачастую проверяются перед приёмом на работу.
Правда, в данном цикле статей этот метод мы рассматривать не будем. Можете ознакомиться с прошлой версией статьи по четвёртому типу 24 заданий, в котором большую часть мы решали с помощью двух указателей.
Помните, что выбор метода — это лишь рекомендация. На практике используйте тот подход, который кажется вам более понятным и надёжным. А на реальном экзамене нелишним будет проверить ответ альтернативным способом.
Типизация
В зависимости от того, какое условие предъявляется к искомой последовательности символов, можно разделить 24 задания на 4 типа.
Первый тип — задания, в которых нужно найти максимальное количество идущих подряд последовательностей символов. Это могут быть как заранее заданные последовательности, например, NPO или KLMN. Так и просто некоторые буквы определённого вида: гласная + согласная, символы, представляющие числа в какой-то системе счисления и так далее. Такие задания уверенно решаются с помощью регулярных выражений.
Второй тип — задания с арифметическими выражениями. Здесь строка представляет собой математическое выражение, и нужно найти в нём подстроку с определёнными свойствами. Например, найти самое длинное корректное выражение или подвыражение с максимальным значением. И здесь не обойтись без регулярных выражений. Конечно, есть и другие способы решения, но гораздо проще и быстрее будет использование регулярных выражений.
Третий тип — задания, в которых определённые символы не должны стоять рядом. Типичная формулировка: «Найдите самую длинную подстроку, в которой буквы A и B не стоят рядом». Для таких задач идеально подходит метод замены и разделения строки — мы находим все «запрещённые» комбинации, используем их как разделители и ищем максимальный фрагмент.
Четвёртый тип — задания, в которых символ или подстрока должны встречаться строго определённое количество раз. Например: «Найдите минимальное/максимальное количество идущих подряд символов, среди которых подстрока X встречается не менее/более N раз и при этом содержится ровно M символов Y».
Это пока что самый сложный тип 24 заданий, и он всё чаще попадается на реальном экзамене. Оптимальным выбором для решения заданий четвёртого типа является метод двух указателей. Но часть заданий всё же решается и через регулярные выражения, что полезно, если вы и так уже углубились в их синтаксис.
Под каждый тип у нас отведена своя статья. А далее мы рассмотрим несколько заданий первого типа и выведем алгоритм их решения.
Алгоритм решения
Выводить алгоритм будем сразу по ходу решения. Начнём с такого задания:
«Текстовый файл состоит из символов A, B, C, D, E.
Определите максимальное количество подряд пар символов вида гласная + согласная в прилагаемом файле.»
Решение 24 заданий всегда нужно начинать с небольшого анализа:
- Что содержится в файле?
- Что требуется найти?
Итак, в файле у нас может находиться только 5 букв A, B, C, D, E. Две из них гласные (A, E), три согласные (B, C, D).
Найти нужно идущие подряд пары из гласных и согласных. Только в таком порядке! Например: AB, ABED.
Перед началом решения всегда придумывайте для себя тестовую строку из заданных символов, в которой точно будет подходящая под условие подстрока, а лучше две-три подстроки разной длины.
Возьмем для примера такую строку: «AABECAEABECADA». Здесь действительно есть две подходящие подстроки: «ABEC» и «ABECAD».
Теперь давайте составим регулярное выражение для поиска таких подстрок. Сразу отметим, что для проверки своих шаблонов можете использовать этот сайт.
Для начала определим вид подходящей строки. Она должна состоять из букв A или E, за которыми следуют B, C или D. Можно записать это вот так: «[AE][BCD]».
Такому шаблону будут соответствовать подстроки из двух символов. Но нам нужно как-то сгруппировать такие пары. Для этого воспользуемся незахватывающей группой «(?:…)». Она объединяет содержимое внутри скобок в единый блок, но не сохраняет результат совпадения (в отличие от обычных круглых скобок «( … )»). Получим такую запись: «(?:[AE][BCD])».
Но этого еще недостаточно, мы просто объединили пары в группы. Теперь нужно добавить квантификатор «+». Он применяется ко всей незахватывающей группе «(?:[AE][BCD])». И означает, что вся группа (пара символов) должна повториться 1 или более раз.
В итоге получаем такое выражение: «(?:[AE][BCD])+». Проверим его кодом. Запишем нашу строку и шаблон:
Для поиска воспользуемся функцией finditer() из модуля re:
Посмотрим, что у нас находится в matches:
Видим найденные подстроки и их позиции. Но нам нужно получить сразу самую длинную из них. Для этого будем перебирать все совпадения (match-объекты) из match в списочном включении и искать максимальное значение среди длин групп (match.group()):
В результате получим число 6. Если вы хотите получить не только длину, но и саму подстроку, то используйте такую запись:
Здесь мы ищем максимальную по длине подстроку в списочном включении «[match.group() for match in matches]» и помещаем её в переменную answer.Теперь можно вывести на экран как саму последовательность символов, так и её длину.
Возвращаемся к заданию. Добавим блок кода со считыванием данных из файла:
Получаем число 404. Но это еще не ответ! Мы нашли количество идущих подряд символов гласная + согласная. А в задании требовалось найти количество пар таких букв. Следовательно, нужно поделить полученное число на 2. Получаем значение 202, которое и будет ответом.
Пример 1
На очереди такое задание:
«Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального чётного 14-ричного числа.
В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности.»
Теперь у нас в файле все цифры и заглавные буквы латинского алфавита. Среди них нужно найти максимальное чётное число в 14 системе счисления. Перефразируем: нужно найти самую длинную последовательность, состоящую из символов, которые могут быть в 14 системе счисления. При этом в конце такой последовательности должна стоять чётная цифра.
В 14 системе счисления нам доступны только буквы A, B, C и D. Число у нас должно начинаться с любой цифры или этих четырёх букв, но не с нуля. Далее могут идти любые доступные цифры заданной системы счисления. А в конце должна быть только чётная цифра, это: 2, 4, 6, 8, A или C.
Звучит несложно, давайте составлять регулярное выражение. Начинаем с цифр и буквы A, B, C, D, но не с нуля: «[1-9ABCD]». Сразу после первого символа допускаются все те же буквы и цифры, включая ноль: «[1-9ABCD][0-9ABСD]». И таких символов должно быть 0 и более: «[1-9ABCD][0-9ABСD]*». В конце обязательно должна стоять чётная цифра: «[1-9ABCD][0-9ABСD]*[02468AС]».
Оборачивать в незахватывающую группу тут не нужно! Ведь в прошлом примере мы «стыковали» пары символов, а здесь у нас записано всё число целиком.
Теперь проверим наше выражение на примере такой строки: «X123AX0A12B12X».
Здесь у нас два подходящих под условие чётных числа 14 системы счисления.
А максимальным из них, очевидно, будет «A12B12». В этом задании нам не нужно проверять само значение числа, достаточно, чтобы оно было длиннее остальных.
Запишем регулярное выражение в коде и длину максимальной подстроки:
Получаем число 6, как и ожидалось. Можно смело приступать к работе с файлом:
Запускаем программу и получаем число 2598, которое и пишем в ответ.
Пример 2
Следующее задание будет таким:
Задание 2429
«Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.
Определите в прилагаемом файле последовательность из максимального количества идущих подряд одинаковых букв, начинающуюся и заканчивающуюся чётной цифрой, не содержащую других букв, кроме повторяющихся, не содержащую цифр, кроме первой и последней.
В ответе запишите число — количество символов в найденной последовательности.»
Здесь снова в файле все цифры и буквы латинского алфавита. Найти же нужно последовательность одинаковых букв, которая начинается и заканчивается чётной цифрой.
Что же, просто найти любые буквы между чётными цифрами несложно. А как быть с тем, чтобы повторялась одна и та же буква?
Здесь на помощь придёт довольно интересный синтаксис обращения к содержимому группы в регулярных выражениях. Выглядит он так: сначала идёт группа с захватом содержимого, например, все латинские буквы «(A-Z)», а затем мы ссылаемся на содержимой этой группы такой записью «\1».
В таком случае, если в первой группе будет найдена буква X, то по ссылке «\1» будет находиться она же. Тогда, чтобы найти последовательность одинаковых букв можно использовать такое выражение: «([A-Z])\1+». То есть сначала встречаем любую латинскую букву, а потом требуем, чтобы она повторялась один и более раз.
Осталось лишь приписать с обеих сторон по четной цифре: «[02468]([A-Z])\1+[02468]».
Для проверки выражения сформируем такую строку: «X2AA4XX6BBBB8X».
Запишем в коде:
В итоге получаем ожидаемый ответ 6. Приступаем к работе с файлом:
После завершения работы программы видим на экране число 1212 — это и будет ответ на данное задание.
Пример 3
В заключение рассмотрим такое задание:
«Текстовый файл состоит не более чем из 10^6 символов арабских цифр (0, 1, 2, …, 9).
Определите максимальное количество идущих подряд цифр, расположенных в порядке невозрастания.»
А вот здесь уже регулярные выражения нам не помогут. Проще будет перебирать по 2 числа последовательности и проверять их порядок. Если текущее не больше предыдущего, то будем увеличивать значение счётчика.
Логично предположить, что как только порядок нарушится, значение счётчика обнулится (точнее сказать, сбросится до единицы). Так что максимальное его значение будем фиксировать в отдельной переменной.
В итоге за один проход цикла мы получим нужное нам максимальное количество идущих подряд цифр в порядке невозрастания.
Считываем данные из файла:
И создаём две переменные. В cnt у нас будет храниться текущий счетчик символов последовательности, расположенных в порядке невозрастания. Как только мы определим, что предыдущий символ больше или равен текущему, то к значению cnt прибавим 1. Ведь в таком случае у нас уже два числа в последовательности.
А значение максимальной длины последовательности max_len изначально примем за 0.
Далее идёт цикл с описанной ранее логикой:
В конце выводим значение max_len:
Запускаем программу и видим число 47. Его и запишем в ответ.
Итоги
В конце отметим, что всё же большая часть 24 заданий первого типа решается по одному и тому же шаблонному алгоритму с помощью регулярных выражений. Выглядит он так:
Где:
- *1 — название файла
- *2 — шаблон регулярного выражения
Но всё же для некоторых заданий придётся отступить от шаблона и воспользоваться альтернативными методами решения.
В следующей статье рассмотрим второй тип 24 заданий, в котором нам предстоит работать с арифметическими выражениями.