Обработка символьных строк. Задание 24 ЕГЭ

Способ 1. Решение в блокноте или MS Word

Пример 1: Текстовый файл состоит из символов A, C, D, F и O. 
Определите максимальное количество идущих подряд пар символов вида согласная + гласная  в прилагаемом файле.  Для выполнения этого задания следует написать программу.(kege.ru 4710)

 Для этого способа не нужно программирование, но нужно понимать, что он не универсальный и в некоторых задачах будет слишком трудоемким.

Решение: Открываем текстовый файл. Возможности блокнота очень ограничены, поэтому основные функции, которыми мы будем пользоваться это замена и поиск. Так как нам не важна конкретная буква, важно только чтобы она была согласной или гласной, заменим все гласные на «А», а согласные на «С», с помощью меню правка-> заменить

Таким образом задание преобразовывается в нахождение количества АС. Чтобы проще было считать, заменим «АС» на любой другой символ, например «#». Получим:

Далее путем подбора ищем максимальное количество «#», но если понимаем, что их слишком много, то заменяем, например, 10 «#» на другой символ – «$». Теперь видим, что максимальное количество «$», которое мы нашли, это 9, что будет означать 90 комбинаций «АС» + 5 «#» идущих следом дают ответ 95.

Пример 2. Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество подряд идущих символов, среди которых нет сочетания DD, но есть сочетание FE. Для выполнения этого задания следует написать программу.(kege.ru 5223)

Решение: Данную задачу тоже можно решить, не прибегая к программированию.

Чтобы исключить сочетание DD, сделаем разбивку текста на слова, заменив «DD» на «D   D». В блокноте не очень удобно искать, поэтому скопируем текст в Word. Выполняем поиск FE, ищем максимальную длину слова.

Программный способ решения. Python

Пример: Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих подряд пар символов вида согласная + гласная  в прилагаемом файле.   Для выполнения этого задания следует написать программу.(kege.ru 4710)

Решение:

Первое, с чего начинаем любое задание, это открываем и читаем файл: S = open(‘Путь к файлу\имя файла’).readline()

Так как нам не важно какая именно гласная или согласная должна идти, то упростим задачу заменив все гласные и согласные на какую-то одну букву. Например, все гласные на ‘А’, а все согласные на ‘С’:

s= replace(‘O’, ‘A’)
s= replace(‘D’, ‘C’)
s= replace(‘F’, ‘C’)

Таким образом согласная + гласная это сочетание ‘АС’. Чтобы проще было считать, заменим АС на любой другой символ, например ‘*’:

s= replace(‘AC’, ‘*’)

Чтобы посчитать количество в цикле while будем последовательно искать количество *, начиная с 1:

k= 1
while k*’*’ in s:
  k+=1

Но так как уже после нахождения максимального количества, цикл выполнится еще раз, то выводить будем к-1

Рассмотрим еще один пример: Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество подряд идущих символов, среди которых нет сочетания DD, но есть сочетание FE. Для выполнения этого задания следует написать программу.(kege.ru 5223)

Решение: Так как строка не может содержать DD,  но может содержать D, то можно разбить нашу строку на подстроки при нахождении DD:

while ‘DD’ in s:
s= s.replace(‘DD’, ‘D D’)
s = s.split()

Программный способ решения. Pascal

1. Для решения любой задачи, начала нужно прочитать строку из файла •в языке PascalABC.NET можно выполнить перенаправление потока ввода:

assign( input, ‘k7.txt‘ );  {или: assign(input, ‘C:\Users\Documents\24_demo.txt’); -в зависимости от того, где находится файл}

 readln(s); •программа будет «думать», что читает данные, введённые с клавиатуры (с консоли), а на самом деле эти данные будут прочитаны из файла k7.txt •2. Далее рассмотрим несколько вариантов заданий

Вариант 1. Самая длинная цепочка символов «С»

Введем переменные:

L – длина текущей цепочки букв C

maxL – максимальная длина цепочки букв C на данный момент

Рассмотрим очередной символ строки; если это буква C, увеличиваем L на 1 и, если нужно запоминаем новую максимальную длину; если это не буква C, просто записываем с L ноль:

maxL := 0;

L := 0;

for i:=1 to Length(s) do

  if s[i] = ‘C’ then begin

    L:= L+ 1;          # ещё одна буква C

    if L > maxL then  # возможно, новая максимальная длина

       maxL:= L; end

  else

    L := 0;           # цепочка букв C кончилась  

Вариант 2. Самая длинная цепочка любых символов

•Cложность состоит в том, что мы (в отличие от предыдущей задачи) не знаем, из каких именно символов состоит самая длинная цепочка

Введем переменные: L – длина текущей цепочки одинаковых символов ; maxL – максимальная длина цепочки одинаковых символов на данный момент;

В начальный момент рассмотрим один первый символ (цепочка длины 1 есть всегда!):

maxL:= 1;

L := 1;

Будем перебирать в цикле все символы, начиная с s[1] (второго по счёту) до конца строки, постоянно «оглядываясь назад», на предыдущий символ

for i := 2 to Length(s) do

 обработать пару символов s[i-1] и s[i]

Eсли очередной символ s[i] такой же, как и предыдущий, цепочка одинаковых символов продолжается, и

нужно увеличить значение переменной L; если значение L стало больше maxL, обновляем maxL:

if s[i] = s[i-1] then     # цепочка продолжается  

L :=L+ 1;          # увеличиваем длину

  if L > maxL then begin  # если цепочка побила рекорд

    maxL := L ;   # запоминаем её длину…

    else               

L:= 1           # началась новая цепочка 

Eсли очередной символ не совпал с предыдущим, началась новая цепочка, и её длина пока равна 1 (это значение записывается в переменную L)

Вариант 3. Самая длинная цепочка вида XYZXYZXYZ…

Проверка того, что символ принадлежит цепочке, производится следующим образом. Заметим, что в искомой цепочке чередуется группа из трёх символов (XYZ). Пронумеруем символы искомой цепочки, начиная с нуля.

if ((s[i]=’X’) and (count mod 3=0)) or

       ((s[i]=’Y’) and (count mod 3=1)) or

       ((s[i]=’Z’) and (count mod 3=2))

Если символ не является частью этой цепочки, но может являться её началом (X), длина цепочки принимается равной единице, в противном случае длина обнуляется

else if s[i]=’X’ then count:=1

    else count := 0;

Вариант 4. Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле сразу после буквы A.

Например, в тексте ABCAABADDD после буквы A два раза стоит B, по одному разу — A и D. Для этого текста ответом будет B. Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Решение

Для обозначения каждого символа введем переменную массив [‘A’..’Z’]. Таким образов, нумерация элементов массива будет равна символам латинского алфавита. Теперь когда мы встретим символ “А”, мы на место его последующего символа, будем записывать сколько он раз встречался после буквы “А”.

Изначально, наш массив будет выглядеть следующим образом:

Но как только мы встретим символ “А”, мы на место следующего символа прибавим 1.

Например, если у нас дана последовательность NADK… массив примет вид:

if (s[i] = ‘A’) then
arr[s[i+1]] := arr[s[i+1]] + 1;

После того, как массив будет заполнен, останется только найти среди его элементов максимальный и вывести его индекс, так как он будет указывать на соответствующую букву.

Решение

Особенность задания состоит в том, что нужно будет преобразовать символы строки в числа. Для этого можно воспользоваться функцией strtoint или ord.

Функция StrToInt конвертирует строку с целым значением, такую как ‘123’, в целое Integer.

Функция ORD

Буквы от ‘A’ до ‘Z’ следуют в возрастающем порядке, иными словами, каждая буква имеет порядковое значение, соответствующее ее месту в алфавите. Это порядковое значение может быть получено посредством функции ord.
ord(выражение) – возвращает порядковый номер литеры или значения другого дискретного типа.
ord(‘I’), ord(‘J’). Результат: 73, 74 (код ASCII)

Порядковый номер литеры зависит от используемого кода. Но, независимо от используемого кода, порядковые значения букв следуют по возрастанию:
ord(‘A’) < ord(‘B’) < ord(‘C’) … < ord(‘Z’)

 Порядковые значения цифр также расположены по возрастанию:
ord(‘0’) < ord(‘1’) < ord(‘2’) … < ord(‘9’)
и, более того, порядковые значения соседних цифр отличаются на 1; так, ord(‘9’) – ord(‘0’) = 9. Отсюда следует, что численное значение цифры d (типа char) может быть получено так
value := ord(d) – ord(‘0’).

Таким образом, получаем программу

Задания для самостоятельного решения

1. Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите длину самой длинной последовательности, состоящей из символов Y. Хотя бы один символ Y находится в последовательности.

Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Задание 24

2. Текстовый файл 24-5.txt содержит последовательность из символов «(»и «)», всего не более 10⁶ символов. Определите максимальное количество подряд идущих открывающих скобок «(» в этом файле.

3. Текстовый файл 24-j5.txt состоит не более чем из 10⁶ символов S, T, O, C, K. Определите максимальное количество подряд идущих комбинаций «KOT»

4. В текстовом файле k8.txt находится цепочка из не более чем 10⁶ символов, в которую могут входить заглавные буквы латинского алфавита A…Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Выведите сначала символ, из которого строится цепочка, а затем через пробел – длину этой цепочки. Если таких цепочек (максимальной длины) несколько, выведите информацию о первой встретившейся цепочке.

5. Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле сразу после буквы E.

Например, в тексте EBCEEBEDDD после буквы E два раза стоит B, по одному разу — E и D. Для этого текста ответом будет B.

Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Задание 24

6. Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле между двумя одинаковыми символами.

Например, в тексте CBCABABACCC есть комбинации CBC, ABA (два раза), BAB и CCC. Чаще всего — 3 раза — между двумя одинаковыми символами стоит B, в ответе для этого случая надо написать B.

Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Задание 24

7. Текстовый файл состоит не более чем из 10⁶ десятичных цифр. Найдите максимальную длину последовательности, каждые две соседние цифры в которой в сумме дают значение не меньшее 10.

Например, в последовательности 1567543853 есть две такие последовательности 5675 и 385.

В качестве ответа укажите максимальную длину найденной последовательности.

Для выполнения этого задания следует написать программу.

Файлы к заданию: 24.txt

8. Текстовый файл состоит не более чем из 10⁶ десятичных цифр. Восходящей последовательностью называется последовательность цифр, в которой каждая цифра меньше следующей за ней. Например, в последовательности 7238903278 три таких последовательности – 2389, 03 и 278. Длиной последовательности называется количество входящих в нее цифр.

Определите сколько в файле восходящих последовательностей длиной 5, не входящих в восходящие последовательности большей длины.

Для выполнения этого задания следует написать программу.

Файлы к заданию: 24.txt

9. Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество подряд идущих символов, среди которых нет сочетания TT, но есть сочетание AB.

Для выполнения этого задания следует написать программу.

10. В текстовом файле находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите максимальную длину цепочки вида DEDEDE…. (состоящей из фрагментов DE, последний фрагмент может быть неполным).

11. Текстовый файл состоит из символов A, B, C, D, E, F.

Определите максимальное количество подряд пар символов вида гласная + согласная в прилагаемом файле.

Для выполнения этого задания следует написать программу.