Задачи с повторяющимися комбинациями в №24

Задачи с повторяющимися комбинациями в №24

👋 После недавнего анбоксинга №24 мне в личку прилетели вопросы по поводу нескольких способах, которые я предлагал в посте. И что-то я подумал: а расскажу всем подробно про каждый, поэтому в планах целая серия постов об этом задании))

👉 Повторяющиеся комбинации (сейчас)

🔜 Запрещённые комбинации

🔜 Ограниченное количество

🔜 Сложные шаблоны

🔜 Несколько строк

🔜 Частотный анализ

Первый тип - повторяющиеся комбинации. Рассматривать будем только на примере, никакой теории, сплошная практика! Покажу все 3 способа! Возьмем задачу №24.10005 с bank-kege.ru

Условие:

Текстовый файл состоит из символов из набора A, B, C. Найдите максимальное количество подряд идущих пар символов АС или АВ. Искомая подстрока может включать только пары АВ, только пары АС или содержать одновременно как пары АС, так и пары АВ.

1⃣ Цикл while с оператором in

Идея: Заменяем AC на AB (или наоборот), чтобы искать только пары AB. Заводим переменную для количества, и пока к количеству можно прибавлять 1, прибавляем. Можно прибавлять, значит, подстрока, где подряд идущих AB на 1 больше, всё еще содержится в строке.

Код:

s = open('24.10005.txt').readline().strip()

s = s.replace('AC', 'AB')

cnt = 0

while (cnt + 1) * 'AB' in s:

cnt += 1

print(cnt)

2⃣ Цикл for с шагом 2

Идея: Перебираем индексы строки, наша пара - 2 подряд идущих символа s[i] и s[i + 1]. Чтобы в следующий раз смотреть следующую пару, идем с шагом 2. Если под этими индексами нужная пара AB или AC - текущее количество увеличиваем на 1 и обновляем максимум, иначе - сбрасываем счетчик. Нюанс в том, что например, в строке BABAB самая длинная цепочка нужных пар начинается с 1 индекса, соответственно, необходимо пройтись по строке 2 раза и посмотреть отдельно пары с четных и нечетных индексов. Реализовать можно как угодно, я просто использую внешний цикл, в котором будет всего 2 итерации.

Код:

s = open('24.10005.txt').readline().strip()

max_cnt = 0

for start in 0, 1:

cur_cnt = 0

for i in range(start, len(s) - 1, 2):

if s[i] == 'A' and s[i + 1] in 'BC':

cur_cnt += 1

max_cnt = max(max_cnt, cur_cnt)

else:

cur_cnt = 0

print(max_cnt)

3⃣ Регулярные выражения

Идея: Составим регулярку: комбинация AB или (|) AC, берем выбор в скобки и повторяем сколько угодно раз, без разницы с помощью "+" или "*". Потом методом finditer находим самую длинную подходящую строку. Важно: в ответ записываем не длину строки, а количество пар, то есть длину делим пополам!

Код:

from re import *

s = open('24.10005.txt').readline().strip()

reg = r'(AB|AC)+'

mx = max(len(i.group()) for i in finditer(reg, s))

print(mx / 2)

Если разобраться с этими тремя способами, первый тип можно считать полностью убитым! Никогда не останавливайтесь на каком-то одном варианте, если хотите на ЕГЭ балл за №24, вам необходимо не просто покрыть максимальное количество имеющихся задач, главное - научить свою голову думать по-новому, чтобы решить не только то, что было, а еще и то, что будет!

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

🔥 Цикл while с оператором in

💯 Цикл for с шагом 2

😁 Регулярные выражения

А самостоятельно попрактиковаться в таких задачах, или собрать подборку для учеников, можно с помощью bank-kege.ru, просто в базе выбираете фильтр "Повторяющиеся комбинации" в поле "Тип", рекомендую идти по возрастанию сложности)

#информатика

#задание24