Задача 24 ЕГЭ по информатике (обработка строк). Как решать на питоне.
Задача 24 ЕГЭ по информатике (обработка строк). Как решать на питоне.
Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне
Я просмотрел задание 24 по информатике на сайте "Решу ЕГЭ" и пришел к двум выводам.
Вывод первый: задания для ЕГЭ составляют старые мастодонты (ещё более старые, чем я), которые обучались программированию ещё в прошлом веке и ничего, кроме паскаля, не знают (ну, может, ещё знают основы сиплюсплюса). Так и вижу, как они при составлении задания довольно потирают ручки и представляют, как бедные ученики будут сравнивать строчечки буковка за буковкой и напишут паскаль-простыню на десяток-другой строк.
Вывод второй, удручающий: решения задач, которые можно найти в интернете, достаточно часто пишут такие же старые мастодонты, которые пишут на питоне программы а-ля паскаль и не подозревают о возможностях питона, которые позволяют решить большинство задач по обработке символьных строк буквально в три-четыре строчки. Из-за этого ученики обучаются паскалевскому мышлению и тоже "застревают в прошлом веке".
В этой статье я попытаюсь рассказать о том, как составлять совсем короткие программы для решения задач, предлагаемых на ЕГЭ. В решениях будут часто использоваться генераторы списков и условные выражения. Давайте познакомимся с ними (очень коротко).
Генераторы списков
Генератор списков - это следующая конструкция:
[выражение for переменная in нечто]
или
[выражение for переменная in нечто if условие]
Как это работает?
"Нечто" - это нечто, откуда можно получить последовательность значений. Если это список или кортеж, то мы получим последовательность их элементов. Если это файл, то мы получим последовательно его строки. Если строка - получим последовательно символы в этой строке. Если множество - элементы множества. Ах да, я забыл про конструкцию range() - но с ней, полагаю, всё ясно.
Каждое очередное значение присваивается переменной, и вычисляется выражение. Из значений этих выражений формируется новый список.
Если в генераторе присутствует if, то в сформированный генератором список будут включены только те значения, для которых условие, записанное после if, истинно.
Пусть в списке a содерхатся целые числа. Тогда список, содержащий квадраты этих чисел, можно получить следующим образом:
[x**2 for x in a]
А выражение
[x**2 for x in a if x%2==0]
даст список квадратов только чётных чисел из списка a. Согласитесь, что это выражение вполне понятно и короче, чем код вроде
b=[]
for x in a:
if x%2==0:
b.append(x**2)
Применение генераторов списков порой позволяет сократить программу до двух-трех строчек.
Условные выражения
Условное выражение - это следующая конструкция:
a if условие else b
Значение этого выражения - это a, если условие истинно, иначе b.
Условные выражения также позволяют сокращать программу (причем не в ущерб её понятности). Так, выражение
r=n+3 if n%2==1 else n//2
заменяет следующий код:
if n%2==1:
r=n+3
else:
r=n//2
Далее разберём конкретные примеры с упором на задачи из ЕГЭ 2023 г. как наиболее актуальные. Но сперва -
Хороший (надеюсь) совет
Хотя Марк Твен говорил: "Нет ничего легче, чем давать хорошие советы, и ничего труднее, чем им следовать", но я всё-таки рискну.
Написав программу для решения задачи, не спешите открывать файл и скармливать ей данные из этого файла. Сперва опробуйте её на строках, для которых ответ очевиден.
Допустим, вам надо найти длину максимальной подстроки, в которой ровно 100 букв Х. Предложите вашей программе следующую строку:
s='XY'*200+'X'
Правильный ответ, очевидно, 201: 100 букв X, 99 букв Y между ними плюс еще две буквы Y слева и справа.
Не лишним будет и проверить строки 'Y'*1000+'X'*200 и 'X'*200+'Y'*1000, чтобы убедиться, что программа находит требуемую строку, если она находится в самом начале или в самом конце файла. (Некоторые решения, которые я встречал в интернете, таких строк не обнаруживают: если бы я составлял задания ЕГЭ, я бы непременно поставил нужную строку в начале или в конце - из вредности.)
И только убедившись в том, что тесты обрабатываются правильно, открывайте файл и получайте решение.
А теперь - к задачам.
Подстрока, содержащая ровно N символов X.
Таких задач в прошлом году было очень много. Кроме того, эта задача включена и в демонстрационный вариант ЕГЭ 2024 г.
Суть задачи следующая. Имеется символьная строка длиной миллион символов или около того. Требуется определить длину самой длинной (или, наоборот, самой короткой) подстроки этой строки, которая содержит ровно N символов X (или T, или U, или ещё какую-нибудь иную букву). Число N обычно равно 100 или около того.
Рассмотрим алгоритм решения. Самая длинная подстрока, очевидно, должна быть заключена между двумя символами Х. Тогда её невозможно увеличить: при расширении её на символ влево или вправо в ней появится ещё один символ Х. Возможно также, что подстрока "упирается" одним из своих концов в начало или конец исходной строки.
Составим p - список индексов всах символов Х в строке. В нашей подстроке должно быть N символов X. Пусть номера этих символов - от 1 до N. Тогда символ слева от подстроки - 0, а справа - N+1. Разность номеров обрамляющих символов равна N+1. Длина же нашей подстроки - это p[N+1]-p[0]-1.
Чтобы учесть "краевые эффекты", добавим в наш список индексов слева число -1, а справа - длину исходной строки.
Теперь надо найти все возможные разности вида p[i+N+1]-p[i]-1 и выбрать максимальную из них.
Строка минимальной длины, содержащая ровно два символа Х, очевилно, начинается и заканчивается именно символами Х. Этих символов N штук, если самой левый символ имеет номер 1, то самой правый - N, и разность их номеров равна N-1. Длина строки будет равна p[N]-p[1]+1.
1. Построим p - список позиций, на которых находится символ X в исходной строке. Если требуется подстрока максимальной длины, то добавляем в начало списка число -1, а в конец - число, равно длине исходной строки.
2. Если требуется подстрока максимальной длины - ищем разности в списке позиций с шагом N+1, выбираем максимальную из этих разностей и отнимаем единицу. Если требуется подстрока минимальной длины - ищем разности в списке позиций с шагом N-1, выбираем минимальную из этих разностей и прибавляем единицу.
Займемся программной реализацией этого алгоритма для N=100. Список позиций можно получить с помощью следующего генератора списков:
p=[i for i in range(len(s)) if s[i]=='X']
Список разностей получим с помощью другого генератора списков:
[p[i+step]-p[i] for i in range(len(p)-step)]
step - это шаг, с которым мы вычисляем разности. Для поиска самой длинной подстроки step должен быть на единицу больше требуемого количества символов, а для поиска самой короткой - на единицу меньше.
Вот программы для определения длины максимальной и минимальной подстрок, содержащих ровно 100 символов Х:
# максимальная подстрока, содержащая 100 букв X
s = open('24.txt').readline()
p=[-1]+[i for i in range(len(s)) if s[i]=='T']+[len(s)]
print(max(p[i+101]-p[i]-1 for i in range(len(p)-101)))
# минимальная подстрока, содержащая 100 букв X
s = open('24.txt').readline()
p=[i for i in range(len(s)) if s[i]=='T']
print(min(p[i+99]-p[i]+1 for i in range(len(p)-99)))
Подстрока, содержащая ровно N пар символов X
Эта задача очень похожа на предыдущую. Требуется найти длину самой длинной (или самой короткой) подстроки, которая содержит ровно N пар символов X. Решение этой задачи тоже примерно такое же.
Сперва составим список индексов начал пар 'XX' в нашей строке:
p=[i for i in range(len(s)-1) if s[i:i+2]=='XX']
Максимально длинная подстрока (если она не в самом начале или не в самом конце исходной строки) содержится между парами 'XX', её границы - в середине этих пар:
...XXAAA...XX.AAAXX...
Если расширить эту подстроку на один символ влево или вправо, в ней появится ещё одна пара 'XX'.
А самая короткая подстрока начинается и заканчивается такими парами. При сокращении такой подстроки на один символ число пар уменьшится.
Программы для решения этой задачи для N=100 следующие:
# максимальная подстрока, содержащая 100 пар букв X
s = open('24.txt').readline()
p=[-1]+[i for i in range(len(s)-1) if s[i:i+2]=='XX']+[len(s)-1]
print(max(p[i+101]-p[i] for i in range(len(p)-101)))
# минимальная подстрока, содержащая 100 пар букв X
s = open('24.txt').readline()
p=[i for i in range(len(s)-1) if s[i:i+2]=='XX']
print(min(p[i+99]-p[i]+2 for i in range(len(p)-99)))
Самое длинное число в системе счисления по некоторому основанию в строке
Задачи этого типа следующие. Имеется строка, состоящая из латинских букв (и, видимо, цифр). Надо найти самую длинную последовательность символов, которая может быть числом, записанным в системе счисления по некоторому основанию.
Решается задача просто. Заменим все символы, которые не могут быть цифрами в указанной системе счисления, на пробелы. Разобъем полученную строку на части с помощью операции split(). Уберем в полученных строках ведущие нули (если они есть). Длина самой длинной из полученных строк и будет ответом на эту задачу.
Если использовать генераторы списков и условные выражения, то можно написать очень короткую программу.
Пусть требуемая система счисления - по основанию 24. Очевидно, в ней 24 цифры: 10 - традиционные, а оставшиеся 14 - буквы английского алфавита от A до N.
На основе исходной строки s составим список символов следующим образом: символы исходной строки, которые являются цифрами в нужной нам системе счисления, оставим как есть, а остальные заменим пробелами. Для этого используем условное выражение. Это выглядит следующим образом:
[c if '0'<=c<='9' or 'A'<=c<='N' else ' ' for c in s]
Этот список превратим в строку с помощью операции join(), а её результат разобъем на не содержащие пробелов строки с помощью операции split().
Теперь найдем длину самой длинной из полученных строк. Для подавления ведущих нулей используем операцию lstrip(). (Операция lstrip() удаляет символы слева, rstrip() - справа, а просто strip() - и слева и справа.)
Получается программа из двух строчек:
s=''.join([c if '0'<=c<='9' or 'A'<=c<='N' else ' ' for c in open('24.txt').readline()])
print(max([len(x.lstrip('0')) for x in s.split()]))
Самая длинная подстрока, в которой некоторые символы не стоят рядом
Вот одна из задач этого типа. Имеется строка из букв английского алфавита. Требуется найти длину самой длинной подстроки, где символы Q, R, и S (в различных комбинациях) не стоят рядом.
В принципе эта задача немного похожа на рассмотренную выше задачу про самую длинную подстроку, содержащую ровно N пар символов XX, только тут N=0 и пары состоят не из одного символа, а из некоторого набора символов. Поэтому и решение схожее.
Построим список индексов пар, состоящий из указанных букв:
[i for i in range(len(s)-1) if s[i] in 'QRS' and s[i+1] in 'QRS' ]
Для учета "краевых эффектов" добавим к этому списку слева число -1, а справа - len(s)-1.
Наш ответ - это максимальная разность двух соседних элементов этого списка.
Программа следующая:
s = open('24.txt').readline()
p=[-1]+[i for i in range(len(s)-1) if s[i] in 'QRS' and s[i+1] in 'QRS' ]+[len(s)-1]
print(max(p[i+1]-p[i] for i in range(len(p)-1)))
Самая длинная последовательность цифр, расположенных в строго убывающем порядке
Имеется строка из цифр. Требуется найти самую длинную подстроку, в которой цифры идут в строго убывающем порядке.
Построим список, в котором для каждой пары соседних цифр в исходной строке стоит звездочка, если левая цифра больше правой, в противном случае - пробел. Преобразуем этот список в строку и разобъем на строки, не содержащие пробелов, с помощью операции split(). Наш ответ - это длина самой длинной подстроки плюс единица.
В итоге получается следующая программа:
s=open('24.txt').readline()
a=''.join(['*' if s[i-1]>s[i] else ' ' for i in range(1,len(s))]).split()
print(max(len(x) for x in a)+1)
Количество подстрок, начинающихся и заканчивающихся некоторой буквой и не содержащих другой буквы
Пример такой задачи: найти в текстовой строке количество подстрок длиной не менее 12, начинающихся и заканчивающихся буквой E и не содержащих внутри себя других букв E и букв F.
Разобьем исходную строку на куски, не содержащие букв E. Каждый такой кусок - это "внутренность" строки между буквами E (естественно, кроме самого первого и самого последнего). Осталось подсчитать количество подстрок длиной не менее 10 (двух букв E в начале и в конце в наших подстроках нет) и не содержащих букв F.
Программа состоит из двух строк:
a=open('24.txt').readline().split('E')
print(len([x for x in a[1:-1] if len(x)>=10 and not 'F' in x]))
Какая буква чаще всего встречается в строке, содержащей наименьшее количество букв G?
Условие этой задачи довольно длинное. Процитирую его целиком.
Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (ABC…Z). Необходимо найти строку, содержащую наименьшее количество букв G (если таких строк несколько, надо взять ту, которая находится в файле раньше), и определить, какая буква встречается в этой строке чаще всего. Если таких букв несколько, надо взять ту, которая позже стоит в алфавите.
Решение этой задачи можно записать короче, чем условие.
Сперва, естественно, надо сформировать список a из строк файла.
Затем можно найти минимальное количество символов G по строкам. Это делается довольно несложно:
ming=min([s.count('G') for s in a])
Теперь составим список только тех строк, число букв G в которых равно минимальному, и выберем из него самый первый элемент. Это и будет той строкой, которая нам нужна.
line=[s for s in a if s.count('G')==ming][0]
Составим список количеств различных букв, которые имеются в данной строке, и выберем из них наибольшее число:
maxlet=max([line.count(c) for c in line])
Получим список букв, которые встречаются чаще всего. Это опять-таки несложно - вот нужное нам выражение:
[c for c in set(line) if line.count(c)==maxlet]
Мы написали set(line) вместо line, чтобы каждая буква входила в наш список только один раз.
Осталось отсортировать этот список, выбрать из него последний элемент и отпечатать его.
Вот программа целиком:
a=[s for s in open('24.txt')]
ming=min([s.count('G') for s in a])
line=[s for s in a if s.count('G')==ming][0]
maxlet=max([line.count(c) for c in line])
print(sorted([c for c in set(line) if line.count(c)==maxlet])[-1])
Как я и обещал, решение получилось существенно короче условия - спасибо генераторам списков, которые здесь использованы в каждой строке.
Максимальное расстояние между одинаковыми буквами в одной строке
Условие задачи следующее. Есть текстовый файл, состоящий из строк. Требуется найти максимальное расстояние между одинаковыми буквами в строке - но только в тех строках, которые содержат менее 25 букв G.
Сначала напишем функцию, которая находит максимальное расстояние между двумя одинаковыми буквами в строке. Алгоритм простой: ищем разность между самым правым и самым левым положением каждой буквы, которая встречается в строке. Если повторяющихся букв нет, функция вернет 0.
Получается не очень сложно:
def mras(s):
return max([s.rfind(c)-s.find(c) for c in set(s)])
Как и в прошлой задаче, мы написали не s, а set(s) - чтобы каждая буква обрабатывалась по одному разу.
Есть небольшая опасность: если в файле есть пустые строки, то при вычислении функции mras возникнет ошибка выполнения - попытка вычислить max от пустой последовательности. Если такая неприятность случится, то в функцию надо добавить проверку, не является ли строка s пустой.
Теперь всё очень просто: составляем список из только тех строк файла, которые содержат менее 25 букв G, вычисляем значение нашей функции для каждой из таких строк и находим максимум.
Вот программа целиком:
def mras(s):
return max([s.rfind(c)-s.find(c) for c in set(s)])
a=[s for s in open('24.txt') if s.count('G')<25]
print(max([mras(s) for s in a]))
Число строк, в которых какая-то буква встречается чаще другой
Есть текстовый файл, разбитый на строки. Требуется подсчитать количество строк, в которых, к примеру, буква E встречается чаще, чем буква A.
Данная задача решается в одну строку:
print(len([s for s in open('24.txt') if s.count('E')>s.count('A')]))
Подстрока, которая начинается и заканчивается символом D, причем между двумя последовательными D должно быть не более двух букв O
Условие следующее: нужно найти длину максимальной подстроки, которая начинается и заканчивается символом D. Между двумя последовательными символами D должно быть не более двух букв O, остальных букв - сколько угодно.
"Разрежем" исходную строку по символам D и не будем учитывать самую левую и самую правую подстроку: одна из них не начинается с D, другая - не заканчивается. Заменим те получившиеся подстроки, в которых содержится более двух символов O, на звездочки.
Теперь "склеим" наши подстроки в одну строку, вставляя между ними символы D, а также присоединим одну букву D слева и одну - справа.
Осталось "разрезать" полученную строку по звездочкам и найти длину самой длинной подстроки. Всё.
Вот программа, реализующая этот алгоритм:
a=[x if x.count('O')<=2 else '*' for x in open('24.txt').readline().split('D')[1:-1]]
s='D'+'D'.join(a)+'D'
print(max([len(x) for x in s.split('*')]))
Максимальная подстрока, которая не содержит сочетания символов XZZY
В задаче требуется найти длину максимальной подстроки, в которой не содержится группы символов XZZY.
Разобьем строку по этой группе символов. Очевидно, подстроки в исходной строке, которые не содержат указанного сочетания, будут на 6 символов длиннее получившихся подстрок: ZZY в начале и XZZ в конце - кроме первой и последней подстрок. Эти две длиннее всего на три символа: у первой подстроки нет символов ZZY в начале, а у последней - символов XZZ в конце.
Решение следующее:
d=[len(s) for s in open('24.txt').readline().split('XZZY')]
d[0] -= 3
d[-1] -= 3
print(max(d)+6)
Максимальная подстрока, содержащая ровно одну букву A и ровно одну букву B
Требуется найти в строке, состоящей из заглавных букв английского алфавита, подстроку максимальной длины, в которой ровно одна буква A и ровно одна буква B.
Наша подстрока должна "упираться" своими левым и правым концами в буквы либо A, либо B - тогда её нельзя будет расширить хотя бы на один символ, не увеличив в ней количество требуемых букв. (Правда, возможен вариант, когда подстрока "упирается" либо в начало исходной строки, либо в её конец.)
Составим список всех позиций букв A и B в строке s:
p=[-1]+[i for i in range(len(s)) if s[i] in 'AB']+[len(s)]
Число -1 в начале и len(s) в конце нужны, чтобы учесть "краевые эффекты".
Рассмотрим четверку позиций p[i], p[i+1], p[i+2], p[i+3]. В каждой из этих позиций в строке s находится либо буква A, либо буква B. Длина подстроки, которая "упирается" слева в pi[i], а справа в p[i+3], равна p[i+3]-p[i]-1. В ней на местах p[i+1] и p[i+2] либо два символа A, либо два символа B, либо символ A и символ B.
Сначала я с помощью операции count() проверял, что в подстроке содержится один символ A и один символ B, но потом сообразил, что можно поступить гораздо проще: символы в позициях p[i+1] и p[i+2] должны быть разными.
Получилась вот такая программа:
s=open('24.txt').readline()
p=[-1]+[i for i in range(len(s)) if s[i] in 'AB']+[len(s)]
print(max([p[i+3]-p[i]-1 for i in range(len(p)-3) if s[p[i+1]]!=s[p[i+2]]]))
Буква, которая чаще всего встречается после буквы A (или между двумя одинаковыми буквами)
В данной задаче требуется найти, какая буква чаще всего встречается в символьной строке после буквы A. Возможны варианты: найти букву, которая чаще всего встречается после двух одинаковых букв, или между двумя одинаковыми буквами.
Задача решается в три приема: составить список нужных букв, найти, сколько раз встречается каждая буква, и выбрать максимальное число, а потом найти букву (или буквы), которая встречается данное число раз.
Максимальное количество появлений буквы в списке a можно найти так:
m=max([a.count(c) for c in set(a)])
Можно было бы написать и in a, но вариант in set(a) работает гораздо быстрее, так как каждая буква обрабатывается лишь один раз, а не многократно.
Список самых частых букв из списка a можно получить так:
[c for c in set(a) if a.count(c)==m]
А вот тут писать set(a), а не просто a, обязательно: иначе буква появится в списке m раз.
Вот программа, которая находит самую частую букву после буквы A:
s=open('24.txt').readline()
a=[s[i] for i in range(1,len(s)) if s[i-1]=='A']
m=max([a.count(c) for c in set(a)])
print(*[c for c in set(a) if a.count(c)==m])
Если нужно найти самую часто встречающуюся букву между двумя одинаковыми буквами, то вторую строчку надо заменить на следующую:
a=[s[i] for i in range(1,len(s)-1) if s[i-1]==s[i+1]]
Составление списка букв, которые встречаются после двух одинаковых букв, оставим читателю в качестве упражнения.
Самая длинная подстрока, в которой каждая из букв UVWXYZ встречается не более ста раз.
Приведу текст программы без комментариев: прочитавшим предыдущее всё должно быть понятно.
s=open('24.txt').readline()
letters='UVWXYZ'
ndx=[-1]+[i for i in range(len(s)) if s[i] in letters]+[len(s)]
cnts={}
for c in letters:
cnts[c]=0
a,b=0,1
maxlen=ndx[b]-ndx[a]-1
while b<len(ndx)-1:
c=s[ndx[b]]
cnts[c]+=1
b+=1
while max(cnts.values())>100:
a+=1
c=s[ndx[a]]
cnts[c]-=1
maxlen=max(maxlen,ndx[b]-ndx[a]-1)
print(maxlen)
Вместо заключения
Интересных задач по обработке строк много. Я рассмотрел в основном задачи, которые были в ЕГЭ 2023 г. и некоторые другие. Надеюсь в дальнейшем дополнять эту статью другими примерами.
Как говорится, продолжение следует...
(c) Ю.Д.Красильников, 2024 г.
Комментарии
Отправить комментарий