Задание 24
Каналы авторов Физмат на сотку, Я обязательно сдам ЕГЭ по ИНФОРМАТИКЕ
Сложность: повышенный уровень
Время на решение одной задачи: около 15 минут
Начальные знания: основы python, генераторы массивов
Статьи по другим заданиям: тык
Другая статья по этому заданию: тык
Что из себя представляет задание?
Данная задача проверяет умение работать со строками, находить наибольшую (наименьшую) подпоследовательность
1) Задание на одну строку
Давайте рассмотрим задание из демоверсии 2021 года.
Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.
Откроем файл, приложенный к этому заданию
f = open('24.txt')Считаем в переменную s первую строку из файла (в нашем случае единственную)
s = f.readline()
Давайте заведём счётчик количества подходящих элементов k и переменную для хранения длины максимальной подходящей подпоследовательности m
k = 1 m = 0
Запустим цикл for длины строки s, с помощью функции len(s). Стоит помнить, что мы будем проверять сразу два элемента, поэтому от len(s) надо отнять 1
for i in range(len(s)-1):
Давайте будем делать проверку, если s[i] не равно s[i+1], то к k будем прибавлять 1, иначе будем находить максимум из максимальной длины и новую длины с помощью функции max() и скидывать k до 1
if s[i] != s[i+1]:
k += 1
else:
m = max(m, k)
k = 1print(m)
35
f = open('24.txt')
s = f.readline()
k = 1
m = 0
for i in range(len(s)-1):
if s[i] != s[i+1]:
k += 1
else:
m = max(m, k)
k = 1
print(m)Тонкости, которые могут помешать вам решать это задание:
1)Стоит помнить, когда мы считываем сразу два символа, следует задать начальное значение переменной k ровное 1, потому что длина подпоследовательности будет считаться без первого элемента
Разберём 24 задание из демоверсии 2022 года:
Текстовый файл состоит из символов P, Q, R и S. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P. Для выполнения этого задания следует написать программу.
Откроем файл и считаем все символы строки в переменную s. Также заведём переменные k и m для подсчёта количества и максимальной длины подходящей строки соответственно
f = open('24.txt')
s = f.readline()
k = 1
m = 0Давайте будем проверять если s[i] равно P и s[i+1] равно P, то только тогда будем сравнивать наш результат с максимальной длиной, иначе будем прибавлять к k 1
for i in range(len(s)-1):
if s[i] == 'P' and s[i+1] == 'P':
m = max(m, k)
k = 1
else:
k += 1print(m)
188
f = open('24.txt')
s = f.readline()
k = 1
m = 0
for i in range(len(s)-1):
if s[i] == 'P' and s[i+1] == 'P':
m = max(m, k)
k = 1
else:
k += 1
print(m)Разберём возможную ошибку, которая может возникнуть при решении этого задания:
Давайте найдём ошибку в этой программе:
f = open('24.txt')
s = f.readline()
k = 1
m = 0
for i in range(len(s)-1):
if s[i] != 'P' and s[i+1] != 'P':
k += 1
else:
m = max(m, k)
k = 1
print(m)Давайте рассмотрим работу оператора and. Сначала он вычисляет значение слева, и если оно ложно, то уже не вычисляет значение справа. Поэтому когда нам встречается одиночная P, то длина будет сброшена.
Поэтому, используя эту программу, мы получим неправильный ответ.
Чтобы этот способ работал корректно, надо видоизменить программу:
f = open('24.txt')
s = f.readline()
k = 1
m = 0
for i in range(len(s)-1):
if s[i] == 'P':
if s[i+1] == 'P':
m = max(m, k)
k = 1
else:
k += 1
else:
k += 1
print(m)Теперь если элемент равен P, то проверяется условие для следующего элемента.
Разберём такую вариацию 24 задания.
Разберём решение этой задачи 3 способами:
Начнём с самого очевидного и надёжного способа:
f = open('24-j5.txt')
s = f.readline()
k = 0
for i in range(len(s)-2):
if s[i] == 'K' and s[i+1] == 'O' and s[i+2] == 'T':
k += 1
print(k)
8192
Думаю, не стоит останавливаться на работе этого алгоритма.
Но что если я скажу вам, что в python есть функция, которая заменяет этот алгоритм одной строчкой. Да такая функция есть, и это функция count()
Давайте рассмотрим решение этой задачи с помощь функции count().
f = open('24-j5.txt')
s = f.readline()
print(s.count('KOT'))Как можно заметить, функция count() находит количество всех совпадений в строке s, в данном случае строку 'KOT'.
Стоит заметить, что у функции count() есть один большой минус.
Давайте вызовем функцию count() от такой строки s
s = 'OTOTOACDF'
print(s.count('OTO'))Получим такой результат работы:
1
На самом деле количество подходящих строк равно 2. Разберёмся, почему возвращаемый ответ некорректен. На самом деле функция count() считает непересекающиеся совпадения, поэтому когда часть слова может являться началом нового, то лучше пользоваться стандартными методами
Рассмотрим ещё один способ решения этого задания с помощью регулярных выражений.
Регулярные выражения:
Чтобы понять этот способ решения, немного теории. Для использования регулярных выражений нужно подключить библиотеку re
import re
Для решения этого задания нам понадобиться функция re.findall(), которая принимает первым аргументом регулярное выражение, вторым строку, в которой будет произведён поиск, а возвращает массив из подходящих элементов.
Например, мы хотим найти количество символов A в строке 'ACBFKADHBAAA'
Для этого достаточно в регулярном выражении указать символ A.
s = 'ACBFKADHBAAA'
result = re.findall('A', s)Теперь в result записан массив, состоящий из элементов A. Для наглядности выведем result
print(result)
['A', 'A', 'A', 'A', 'A']
Чтобы найти количество возьмём длину массива result с помощью функции len()
print(len(result))
5
Но, что если мы хотим найти длину последовательности, состоящих минимум из двух элементов A? Для этого достаточно в регулярном выражении после A указать {2,}, это означает, что символ A должен встречаться в строке минимум 2 раза.
s = 'ACBFKADHBAAA'
result = re.findall('A{2,}', s)
print(result)['AAA']
Если мы хотим указать лимит повторений, то достаточно указать его вторым аргументом в фигурных скобках:
s = 'ACBFKADHBAAA'
result = re.findall('A{2,3}', s)
print(result)['AAA']
Больше про работу регулярных выражений тык
Вернёмся к нашей задаче. Для её решение необходимо в регулярном выражении функции re.fndall() указать строку KOT
import re
f = open('24-j5.txt')
s = f.readline()
result = re.findall('KOT', s)
print(len(result))8192
Как и с функцией count() у регулярных выражений есть проблема с поиском подстрок, которые могут являться началом следующей подстроки.
Регулярные выражения помогают укротить код в несколько раз, но далеко не все задачки можно решить, используя их, поэтому не стоит смотреть на регулярные выражения как на панацею.
Давайте разберём задание, которое с помощью регулярных выражений уничтожается в несколько строк.
Решим эту задачу стандартным способом:
Пройдём циклом for по всей строке s. Если 3 подряд идущих символов равно KOT, то будем прибавлять к счётчику k единицу, иначе сбрасывать k до 2
f = open('24-j5.txt')
s = f.readline()
k = 2
for i in range(len(s)-2):
if s[i] == 'K' and s[i+1] == 'O' and s[i+2] == 'T':
k += 1
else:
k = 2
print(k)
2
Но давайте решим это с помощью регулярных выражений. Для этого нам следует в регулярном выражении после комбинации KOT указать число повторений {1,}(минимум 1) и взять KOT в скобки.
Давайте проведём тест на пробной строке
import re
s = 'KOTHHDDKOTKOT'
result = re.findall('(KOT){1,}', s)
print(result)['KOT', 'KOT']
Как можно заметить это не то, что нам нужно. Программа нашла количество подходящих строк, но вывела только искомую строку. Для того, чтобы избежать эту проблему, надо взять всё регулярное выражение в скобки. Тогда программа вернёт в виде кортежа найденную подпоследовательность и искомый строку.
import re
s = 'KOTHHDDKOTKOT'
result = re.findall('((KOT){1,})', s)
print(result)[('KOT', 'KOT'), ('KOTKOT', 'KOT')]
Чтобы получить нужную нам подстроку, надо вывести нулевой элемент каждого кортежа. Это легко сделать с помощью генератора массива:
print([i[0] for i in result])
['KOT', 'KOTKOT']
Теперь можно использовать наш файл. Чтобы найти самую длинную подпоследовательность, можно использовать функцию max().
import re
f = open('24-j5.txt')
s = f.readline()
result = re.findall('((KOT){1,})', s)
print(max([i[0] for i in result]))KOTKOT
Как можно заметить, самая большая последовательность подряд идущих комбинаций KOT равна 2.
1) Задание на множество строк
После хорошей практики на одну строку можно приступить к множеству строк.
Давайте научимся обрабатывать сразу несколько строк на данном примере.
Как обычно откроем приложенный файл
f = open('24-s1.txt')Также заведём переменную k, для подсчёта количества подходящих строк
k = 0
Чтобы считывать строку за строкой, запустим цикл for по всему файлу, который записан в переменную f.
for s in f:
Теперь на каждой итерации в переменную s будет записываться новая строка. Когда мы научились как считывать строку за строкой, нет никаких трудностей решить это задание.
Давайте решим это задание 3 способами:
f = open('24-s1.txt')
k = 0
for s in f:
count_x = 0
count_s = 0
for i in range((len(s))):
if s[i] == 'X':
count_x += 1
if s[i] == 'S':
count_s += 1
if count_x == count_s:
k += 1
print(k)Счётчики count_x и count_s считают количество повторений символов X и S соответственно. С помощью второго цикла будем ввести подсчёты повторений. После этого будет сравнивать count_x и count_s. Если они равны, то будем прибавлять к k единицу.
48
2) С помощью регулярных выражений
import re
f = open('24-s1.txt')
k = 0
for s in f:
if len(re.findall('X', s)) == len(re.findall('S', s)):
k += 1
print(k)В данном случае нам не надо запускать второй цикл, достаточно сравнить длины найденных массивов. В этом случае мы получим такой же ответ
48
f = open('24-s1.txt')
k = 0
for s in f:
if s.count('X') == s.count('S'):
k += 1
print(k)Как можно заметить, данный способ не сильно отличается от способа с регулярными выражениями.
48
Рассмотрим задание, в котором раскрывается вся прелесть регулярных выражений.
Для начала решим данное задание стандартным способ:
f = open('24-s1.txt')
k = 0
for s in f:
for i in range(len(s)-2):
if s[i] == 'F' and s[i+2] == 'O':
k += 1
break
print(k)В данном случае если попадается [i]-ый элемент равен F, а [i+1]-ый равен равен O, то к k будем прибавлять единицу и "ломать" второй цикл, так как нам важно наличие этой комбинации в строке и неважно количество.
757
Давайте рассмотрим решение через регулярные выражения:
import re
f = open('24-s1.txt')
k = 0
for s in f:
if re.findall('F.O', s):
k += 1
print(k)Чтобы обозначить один произвольный символ в регулярном выражении, надо поставить точку.
757
Интересные и сложные задания, которые стоит решить для понимания темы
Данную задачу легче решить на pascal, но мы решим её на python. Для начала всё стандартно. Заведём переменную m, которая будет хранить длину самой большой последовательности между одинаковыми буквами. Будем проходить по каждой строке, в которой символ G встречается меньше 25 раз.
f = open('inf_26_04_21_24.txt')
m = 0
for s in f:
if s.count('G') < 25:Но как нам получить доступ к английскому алфавиту в виде массива или цикла, чтобы было удобно работать. В pascal сделать это легко, но мы не ищем лёгких путей (поэтому мы выбрали python). Чтобы получить ascii код буквы, в python есть функция ord(), которая поможет нам перебрать весь английский алфавит.
for s in f:
if s.count('G') < 25:
for i in range(ord('A'), ord('Z')+1):В pascal есть функции IndexOf() и LastIndexOf(), которые определяют первую и последнюю позицию элемента в строке. В python, как вы могли понять, нет подобного, поэтому создадим что-то похожее сами. Заведём переменные op и end для определения начальной и конечной позиции элемента соответственно. Также запустим третий цикл, который будет проходить по строке s. Каждый раз, когда будем встречать символ chr(i), будем обновлять op и end с помощью функций min() и max().
for s in f:
if s.count('G') < 25:
for i in range(ord('A'), ord('Z')+1):
op = 10**6
end = 0
for j in range(len(s)):
if s[j] == chr(i):
op = min(op, j)
end = max(end, j)Теперь разность переменных op и end будет самая длинная последовательность между одинаковыми буквами. Осталось только сравнивать с самой большой длинной.
for s in f:
if s.count('G') < 25:
for i in range(ord('A'), ord('Z')+1):
op = 10**6
end = 0
for j in range(len(s)):
if s[j] == chr(i):
op = min(op, j)
end = max(end, j)
m = max(m, end-op)1001
Подведём итоги
Мы рассмотрели 24 задачи как на одну строку, так и множество.
Изучили частично регулярные выражения, с помощью которых можно в несколько раз уменьшить код.
каналы авторов Физмат на сотку, Я обязательно сдам ЕГЭ по ИНФОРМАТИКЕ
Статьи по другим заданиям: тык