мария: хороший сайт
21-07-2024
Читать статью
мария: класс
20-07-2024
маша: мяу
Привет! В этой статье мы посмотрим метод двух указателей в 24 Задании ЕГЭ по информатике.
Данный метод является мощным ответом на сложные задачи из 24 Задания ЕГЭ по информатике.
Не будем терять ни минуты приступим к тренировочным задачам по отработке данного метода.
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле минимальное количество идущих подряд символов (длину не прерывной последовательности), среди которых символ F встречается ровно 2025 раз.
Для выполнения следует написать программу.
Напишем программу и потом разберём её.
f=open('24_du_1.txt') s = f.read().strip() l=r=count=0 kmin=10**10 for r in range(len(s)): if s[r]=='F': count += 1 while count == 2025: kmin = min(kmin, r-l+1) if s[l]=='F': count -= 1 l += 1 print(kmin)
В начале программы подвязываемся к файлу. Считываем всё содержимое в переменную s. С помощью функции strip() убираем символ переноса строки, если он там вдруг, случайно, есть.
Далее заводим левую границу l, правую границу r цепочки, которую мы рассматриваем в данный момент времени. Заводим счётчик count, который будет следить за количеством букв F в этой цепочке.
Левая и правая граница находятся на нулевом символе в самом начале. Те символы, где находятся левый и правый указатели так же включаются в рассматриваемую цепочку.
Переменная kmin отвечает за ответ.
В цикле for мы начинаем растягиваем правую границу от начала. С помощью условия мы проверяем, что нам встречается на правой границе. Если встречается символ F, счётчик count увеличивается на 1.
В определённый момент количество букв F в цепочке достигнет нужно значения (2025). Дальше нет смысла тянуть правую границу, ведь нужно найти минимальную цепочку! В подобных задачах дальше пишется цикл while. Всегда нужно подумать, какое условие написать в этом цикле. Мы ищем минимальную цепочку, поэтому ПОКА в счётчике значение 2025, нас всё устраивает, можно проверять цепочку на минимальность для ответа.
Длина цепочки в подобных задачах вычисляется по формуле:
Откуда берётся +1 ?
Посмотрите на рисунок. Левый указатель находится на 0. Правый указатель находится на 2. Если просто найти разницу, то получится 2-0=2. А символов на самом деле три. Поэтому нужно сделать +1.
В подобных задачах всегда нужно думать, когда делать проверку на ответ. Мы выбрали идеальное место. Если мы вошли в цикл While, то сейчас как раз нужно количество символов в нашей цепочке (2025), можно проверять.
Цикл for отвечает за правую границу, за расширение цепочки. Цикл While отвечает за левую границу, за уменьшение цепочки. Мы проверили цепочку на минимальность, и теперь в цикле while пытаемся уменьшить цепочку ещё, ведь нам нужна самая маленькая цепочка, которая отвечает условию задачи.
Если на левой границе встречается символ F, мы двигаем левую границу на 1 символ, и из счётчика count вычитаем 1. Если это произошло, то значение в счётчике count изменится, и мы выйдем из цикла while, можно дальше будет двигать правую границу. Если условие не сработает, то левая граница сдвинется вправо, цепочка уменьшится, но в ней останется нужно количество букв F. Мы добились своей цели, цепочку сделали ещё меньше.
Таким образом, мы будем двигать то правый указатель, то левый указатель. Так проверятся все нужные цепочки и мы получим ответ.
Метод двух указателей работает достаточно эффективно и программа не будет зависать даже на больших объёмах данных.
Похожая задача разобрана в видеоролике:
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной последовательности), среди которых символ B встречается не более 300 раз.
f=open('24_du_1.txt') s = f.read().strip() l=r=count=0 kmax=0 for r in range(len(s)): if s[r]=='B': count += 1 while count > 300: if s[l]=='B': count -= 1 l += 1 if count <= 300: kmax = max(kmax, r-l+1) print(kmax)
В этой задаче нужно найти уже максимальную цепочку. Самое главное в методе двух указателей подумать, какое условие поставить в цикле while и где делать проверку нашей цепочки на максимальность (минимальность).
Как мы говорили, цикл while отвечает за уменьшение цепочки (за сдвиг левой границы), поэтому в этой задаче нет смысла входить в цикл while, пока в счётчике count нужное количество букв B. В этом случае будет двигаться правая граница, и мы будем получать цепочку как можно больше.
В определённый момент мы превысим допустимое значение букв B. В этом случае мы войдём цикл while, чтобы скорректировать цепочку, уменьшить её, т.к. дальше тянуть правую границу бессмысленно.
После цикла while наша цепочка придёт в норму, за счёт сдвига левой границы вправо мы уберём лишнее количество букв B, и можно дальше будет двигать правую границу.
После цикла while мы делаем проверку на максимальность, т.к. именно в этом месте наша цепочка после корректировки содержит нужно количество букв B.
Дополнительную проверку на количество букв B (if count <= 300 ...) именно в этой задаче можно, наверное, не делать, но предлагаю всегда делать ещё раз эту проверку, потому что в некоторых задачах это может с нами сыграть злую шутку.
Смотрите разбор похожей задачи в видеоролике:
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной последовательности), среди которых символ F встречается не более 450 раз, а символ C не встречается совсем.
f=open('24_du_1.txt') s = f.read().strip() l=r=count=0 kmax=0 for r in range(len(s)): if s[r]!='C': if s[r]=='F': count += 1 while count > 450: if s[l]=='F': count -= 1 l += 1 if count <= 450: kmax = max(kmax, r-l+1) else: l=r+1 count=0 print(kmax)
В этой задачке начинаем с проверки, что на правой границе не встретился символ C. Если это так, то решаем, как в прошлый раз.
Если символ всё-таки встретился, нет смысла тянуть дальше правую границу, ведь символ C будет сидеть в цепочке.
Нужно передвинуть левую границу так, чтобы исчез символ C. Мы передвигаем левую границу в R+1.
После этого счётчик count сбрасываем на 0, как будто начинаем наш поиск с самого начала.
Похожую задачу смотрите в видео:
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ A встречается ровно 200 раз, а символ B — ровно 25 раз.
f=open('24_du_1.txt') s = f.read().strip() l=r=countA=countB=0 kmax=0 for r in range(len(s)): if s[r]=='A': countA += 1 if s[r]=='B': countB += 1 while countA > 200 or countB > 25: if s[l]=='A': countA -= 1 if s[l]=='B': countB -= 1 l += 1 if countA == 200 and countB == 25: kmax = max(kmax, r-l+1) print(kmax)
Здесь нужно уже следить за двумя буквами.
Если какая-то буква превысила допустимое значение, нужно корректировать левую границу (уменьшать цепочку).
Похожую задачу посмотрите в видеоролике:
Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Найдите непрерывную цепочку символов наибольшей длины, для которой выполняются два условия:
В ответе укажите длину найденной цепочки. Для выполнения следует написать программу.
f=open('24-157.txt') s = f.read().strip() l=r=count=0 kmax=1 gl='AEIOUY' if s[0] in gl: count = 1 for r in range(len(s)-1): if s[r] <= s[r+1]: if s[r+1] in gl: count += 1 while count>1: if s[l] in gl: count -= 1 l += 1 if count <= 1: kmax = max(kmax, r+1-l+1) else: l=r+1 if s[r+1] in gl: count = 1 else: count=0 print(kmax)
Итак, счётчик count будет следить за количеством гласных в цепочке.
В начале цикла for проверяем, что мы имеем дело с цепочкой, в которой символы идут в алфавитном порядке. Если всё в порядке, действуем по привычной схеме. Правая граница следит за количеством гласных букв, но теперь правая граница - это r+1!
Из-за того, что происходит обращение "к соседу", то идём в цикле for до len(s)-1. Т.к. настоящая правая граница r+1, то когда вычисляем длину цепочки пишем r+1-l+1.
Итак, мы обращаемся к r+1, чтобы проверить гласная там буква или нет, но в самом начале цепочки символ r (он же будет нулевой символ s[0]) никто не проверяет. Поэтому мы должны это сделать в самом начале до цикла for, ведь счётчик count должен показывать актуальную информацию о текущей цепочке.
Разберёмся с веткой else, что будет если символы не идут в алфавитном порядке? Мы должны разрушить эту ситуацию, т.к. дальше тянуть правую границу бессмысленно. Мы сдвигаем левую границу l на r+1. Если мы сдвинем левую границу на r, мы не добьёмся результата. Символы, идущие не в алфавитном порядке останутся в цепочке.
Так же мы должны проверить первый символ новой цепочки на гласную букву, как мы это делали в начале перед циклом for. Мы проверяем именно символ r+1. Сейчас это символ r+1, но на новой итерации это как раз будет символ r, и его нужно проверить.
В kmax мы в начале присвоили 1 для случая, если условие, которое следит за алфавитном порядком, не сработает ни разу, у нас будет ответ 1.
Похожую задачу смотрите в видеоролике:
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых комбинация символов CE встречается ровно 5 раз, а комбинации символов ECE и CEC ни разу не встречаются.
f=open('24_du_1.txt') s = f.read().strip() l=r=count=0 kmax=0 if s[0]+s[1]=='CE': count = 1 for r in range(len(s)-2): if s[r]+s[r+1]+s[r+2] != 'ECE' and s[r]+s[r+1]+s[r+2] != 'CEC' : if s[r+1]+s[r+2] == 'CE': count += 1 while count>5: if s[l]+s[l+1]== 'CE': count -= 1 l += 1 if count==5: kmax = max(kmax, r+2-l+1) else: l=r+1 if s[r+1]+s[r+2]=='CE': count = 1 else: count=0 print(kmax)
Мы начинаем с условия, что в нашей цепочке нет комбинаций "ECE" и "CEC". Идём уже тремя символами.
Правая граница должна следить за парами CE. Далее действуем по стандартной схеме.
Важно понимать, что настоящая правая граница теперь r+2.
Обратите внимание, что пару CE ищем символами r+1 и r+2, но в самом начале цепочки первые два символа тоже нужно проверить. Вдруг именно там находится комбинация CE. Это мы делаем в начале перед циклом for, ведь счётчик count должен хранить всегда актуальную информацию.
Внутри цикла while смещаем стандартно левый указатель на 1. Если на левой границе будет пара CE, достаточно один символ убрать, чтобы пара разрушилась.
Если всё-таки нам встретилась запретная комбинация (ECE или CEC), то мы переносим левую границу так, чтобы разрушить эту комбинацию. Переносим левую границу на r+1.
А так же в ветке else нужно проверить опять первые два символа следующей новой цепочки. Сейчас это символы r+1 и r+2, но на следующей итерации это будут символы r и r+1.
Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых комбинация символов CD встречается ровно 15 раз.
f=open('24_du_1.txt') s = f.read().strip() l=r=count=0 kmin=10**10 for r in range(len(s)-1): if s[r]+s[r+1] == 'CD': count += 1 while count == 15: kmin=min(kmin, r+1-l+1) if s[l]+s[l+1] == 'CD': count -= 1 l += 1 print(kmin)
Удачи на ЕГЭ по информатике в 24 Задании!
