24 (высокий уровень, время – 18 минут)

Тема: Обработка символьных строк

Что проверяется:

Умение создавать собственные программы (10–20 строк) для обработки символьной информации.

1.5.2. Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности.

1.1.3. Строить информационные модели объектов, систем и процессов в виде алгоритмов.

Что нужно знать:

• 
  сначала нужно прочитать строку из файла; эта задача в разных языках программирования решается несколько по-разному
  
• 
  в языке Python удобнее всего использовать такую конструкцию:
  

with open("k7.txt", "r") as F:

s = F.readline()

конструкция with-as – это контекстный менеджер, в данном случае он открывает указанный файл в режиме чтения (второй аргумент «r» при вызове функции open), записывает ссылку на него в файловую переменную F, выполняет тело блока (читает первую строку файла в переменную s) и закрывает (освобождает) файл

• 
  в языке PascalABC.NET можно выполнить перенаправление потока ввода:
  

assign( input, 'k7.txt' );

readln(s);

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

• 
  в языке FreePascal также можно выполнить перенаправление потока ввода, но нужно дополнительно открывать входной поток:
  

assign( input, 'k7.txt' );

reset( input ); { для FreePascal!!! }

readln(s);

• 
  при работе в среде FreePascal нужно убедиться, что в параметрах компилятора включена поддержка длинных символьных строк; на всякий случай стоит добавить в первой строке программы директиву
  

{$H+}

• 
  Среда PascalABC НЕ ПОДДЕРЖИВАЕТ работу с длинными символьными строками, поэтому для решения задачи использовать версию PascalABC.NET, которую можно бесплатно скачать с сайта автора www.pascalabc.net.
  
• 
  в языке С++ используем потоки:
  

#include <fstream>

#include

using namespace std;

int main()

{

ifstream F("k7.txt");

string s;

getline( F, s );

...

}

Самая длинная цепочка символов «С»

• 
  пусть требуется найти самую длинную цепочку символов С (или каких-то других, в соответствии с заданием) в символьной строке s;
  
• 
  можно использовать такой алгоритм:
  

---

while не конец строки:

найти очередную букву C

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

if длина > максимальной длины:

максимальная длина := длина

однако этот алгоритм содержит вложенный цикл и при составлении программы легко запутаться и не учесть какой-то особый случай (например, когда строка состоит только из букв С)

• 
  лучше применить однопроходный алгоритм без вложенного цикла
  

for c in s:

обработать символ c

• 
  будем использовать переменные
  

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

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

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

maxLen = 0

cLen = 0

for c in s:

if c == 'C':

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

if cLen > maxLen: # возможно, новая максимальная длина

maxLen = cLen

else:

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

• 
  проверим правильность работы алгоритма в особых случаях:
  

1. 
   если вся строка состоит из букв C, значение переменной cLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;
   
2. 
   если в строке нет символов C, переменная cLen всегда равна 0, такое же значение будет и в переменной maxLen
   

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

• 
  теперь поставим задачу найти самую длинную цепочку символов в символьной строке s; сложность состоит в том, что мы (в отличие от предыдущей задачи) не знаем, из каких именно символов состоит самая длинная цепочка
  
• 
  если символов в алфавите немного (скажем, A, B и С), то можно с помощью описанного выше алгоритма найти самые длинные цепочки из букв A, B и C, а затем выбрать из них «длиннейшую»; такая идея может сработать при аккуратной реализации, но плохо обобщается на случай, когда возможных символов много (например, используются все заглавные латинские буквы и цифры)
  
• 
  поэтому лучше применить однопроходный алгоритм без вложенного цикла
  
• 
  будем использовать переменные
  

curLen – длина текущей цепочки одинаковых символов

maxLen – максимальная длина цепочки одинаковых символов на данный момент

---

c – символ, из которого строится самая длинная подцепочка

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

maxLen = 1

curLen = 1

c = s[0]

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

for i in range(1,len(s)):

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

• 
  если очередной символ s[i] такой же, как и предыдущий, цепочка одинаковых символов продолжается, и нужно увеличить значение переменной curLen; если значение curLen стало больше maxLen, обновляем maxLen и запоминаем новый базовый символ в переменной c:
  

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

curLen += 1 # увеличиваем длину

if curLen > maxLen: # если цепочка побила рекорд

maxLen = curLen # запоминаем её длину...

c = s[i] # и образующий символ

else:

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

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

• 
  получается такой цикл обработки строки:
  

maxLen, curLen, c = 1, 1, s[0]

for i in range(1, len(s)):

if s[i] == s[i-1]:

curLen += 1

if curLen > maxLen:

maxLen = curLen

c = s[i]

else:

curLen = 1

• 
  проверим правильность работы алгоритма в особых случаях:
  

3. 
   если вся строка состоит из одинаковых символов, значение переменной curLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;
   
4. 
   если в строке нет пар одинаковых символов, переменная curLen всегда равна 1, такое же значение будет и в переменной maxLen
   

Пример задания:

Р-07 (демо-2021). Текстовый файл 24.txt состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.

Решение:

1. 
   считывание из файла и перебор символов аналогичен задачам Р00-Р02 (см. ниже).
   
2. 
   чтобы считать длину цепочки, соответствующей условию, нам нужно будет ввести два счётчика:
   

curLen – длина текущей цепочки (которая сейчас обрабатывается)

maxLen – длина самой длинной на данный момент цепочки в уже обработанной части строки

---

3. 
   обработка строки сводится к тому, что текущая длина цепочки увеличивается, если соседние символы, s[i-1] и s[i], различны; если это не так, сбрасываем длину текущей цепочки в 1
   
4. 
   можно заметить, что эта задача очень напоминает Р-05, только тут обратное условие – нужно искать цепочку, где все соседние символы не одинаковые, а разные, поэтому и решение сводится к изменению условия (см. выделение маркером):
   

with open( "24.txt", "r" ) as F:

s = F.readline()

maxLen, curLen = 1, 1

for i in range(1, len(s)):

if s[i] != s[i-1]:

curLen += 1

if curLen > maxLen:

maxLen = curLen

else:

curLen = 1

print( maxLen )

5. 
   Ответ: 35.
   
6. 
   программа на Паскале:
   

var maxLen, curLen, i: integer;

s: string;

begin

assign(input, '24.txt');

readln(s);

maxLen := 1;

curLen := 1;

for i:=2 to Length(s) do

if s[i] <> s[i-1] then begin

curLen := curLen + 1;

if curLen > maxLen then

maxLen := curLen;

end

else

curLen := 1;

writeln(maxLen);

end.

7. 
   программа на C++:
   

#include

#include

#include

using namespace std;

int main()

{

ifstream F("24.txt");

string s;

getline( F, s );

int maxLen = 1, curLen = 1;

for( int i = 1; i < s.length(); i++ )

if( s[i] != s[i-1] ) {

curLen ++;

if( curLen > maxLen )

maxLen = curLen;

}

else curLen = 1;

cout << maxLen;

}

Пример задания:

Р-06. В текстовом файле k8.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A…Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Для каждой цепочки максимальной длины выведите в отдельной строке сначала символ, из которого строится эта цепочка, а затем через пробел – длину этой цепочки.

Решение:

1. 
   особенность этой задачи в сравнении с Р-05 состоит в следующем: если найдено несколько цепочек одинаковой максимальной длины, для каждой из них нужно вывести символ, из которого состоит цепочка, и длину цепочки
   
2. 
   это значит, что для хранения символа нужна не одна переменная, а массив (в Python – список); если найдена первая цепочка (выполнено условие )
   
3. 
   итак, теперь c – это массив (список); когда найдена первая цепочка максимальной длины (на данный момент), в этот массив записывается символ этой цепочки; если же найдена новая цепочка такой же длины, в массив добавляется символ этой цепочки
   
4. 
   таким образом, в конце прохода в массиве c находятся все символы, из которых состоят самые длинные цепочки, и остаётся вывести их на экран; справа от каждого символа выводится длина цепочки:
   

---

for c1 in c:

print( c1, maxLen )

5. 
   вот полная программа (изменения в сравнении с решением задачи Р-05 выделены):
   

with open( "k8.txt", "r" ) as F:

s = F.readline()

maxLen, curLen, c = 1, 1, [s[0]] # c – массив из одного символа

for i in range(1, len(s)):

if s[i] == s[i-1]:

curLen += 1

if curLen == maxLen: # новая цепочка максимальной длины

c.append( s[i] ) # добавить символ в массив

elif curLen > maxLen:

maxLen = curLen

c = [s[i]] # c – массив из одного символа

else:

curLen = 1

for c1 in c: # для всех символов в массиве

print( c1, maxLen ) # вывести символ и длину

Решение (программа на языке Pascal):

1. 
   проблема состоит в том, что мы не знаем, сколько цепочек максимальной длины может быть в файле; тут нужен динамический массив (список), для этого далее мы будем использовать язык PascalABC.NET, в котором есть тип данных List (список)
   
2. 
   вначале создаём новый список и записываем у него первый символ строки:
   

var c := new List;

c.Add( s[1] );

3. 
   если нашли новую (не первую) цепочку максимальной длины, добавляем новый символ в список:
   

c.Add( s[i] );

4. 
   если нашли новую самую длинную цепочку с длиной бОльшей, чем все предыдущие, очищаем список и добавляем в него новый символ.
   

c.Clear;

c.Add( s[i] );

5. 
   после окончания обработки нужно вывести все символы и длины цепочек, удобнее всего использовать для этого цикл foreach; получается почти так же, как и на Python:
   

foreach var c1 in c do

writeln( c1, ' ', maxLen );

6. 
   вот полная программа:
   

var maxLen, curLen, i: integer;

s: string;

begin

assign(input, 'k8.txt');

readln(s);

maxLen := 1;

curLen := 1;

var c := new List;

c.Add( s[1] );

for i:=2 to Length(s) do

if s[i] = s[i-1] then begin

curLen := curLen + 1;

if curLen = maxLen then begin

c.Add( s[i] );

end

else if curLen > maxLen then begin

maxLen := curLen;

c.Clear;

c.Add( s[i] );

end

end

else

curLen := 1;

foreach var c1 in c do

writeln( c1, ' ', maxLen );

end.

Решение (программа на языке C++):

---

Смотрите также файлы

• Закон всемирного тяготения.doc

• Задание Ознакомьтесь с теоретическим материалом.docx

• Составьте подборку упражнений наиболее способствующих развитию лексического строя речи.docx

• При воспалении околоносовых пазух наиболее вероятно развитие внутричерепных осложнений.docx

• Почему у людей возникает зависимость от компьютерных игр.docx