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длина := длина текущей цепочки букв Cif длина > максимальной длины:максимальная длина := длинаоднако этот алгоритм содержит вложенный цикл и при составлении программы легко запутаться и не учесть какой-то особый случай (например, когда строка состоит только из букв С)

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

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

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

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

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

maxLen = 0cLen = 0for c in s:if c == 'C':cLen += 1 # ещё одна буква CifcLen > maxLen: # возможно, новая максимальная длинаmaxLen = cLenelse:cLen = 0 # цепочкабукв C кончилась

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

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

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

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

curLen – длина текущей цепочки одинаковых символов maxLen – максимальная длина цепочки одинаковых символов на данный моментc – символ, из которого строится самая длинная подцепочка

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

---

maxLen = 1curLen = 1c = 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 # увеличиваем длинуifcurLen > 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 += 1if curLen > maxLen:maxLen = curLenc = 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, 1for i in range(1, len(s)):if s[i] != s[i-1]:curLen += 1if curLen > maxLen:maxLen = curLenelse:curLen = 1print( maxLen )

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

var maxLen, curLen, i: integer; s: string;beginassign(input, '24.txt'); readln(s);maxLen := 1;curLen := 1;for i:=2 to Length(s) do if s[i] <> s[i-1] then begincurLen := curLen + 1;if curLen > maxLen thenmaxLen := curLen;endelsecurLen := 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 += 1ifcurLen == maxLen: # новая цепочка максимальной длиныc.append( s[i] ) # добавить символ в массивelif curLen > maxLen:maxLen = curLenc = [s[i]] # c – массивизодногосимволаelse:curLen = 1forc1 inc: # для всех символов в массиве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;beginassign(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 begincurLen := curLen + 1;if curLen = maxLen then beginc.Add( s[i] );end else if curLen > maxLen then beginmaxLen := curLen;c.Clear;c.Add( s[i] );end endelsecurLen := 1;foreach var c1 in c do writeln( c1, ' ', maxLen ); end.Решение (программа на языке C++):

---

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

• Решение Группировка по возрастанию 1, 3, 7, 10, 14.docx

• Памятка Что нужно знать о татуировке.docx

• Курсовая работа по предмету Патологическая анатомия.rtf

• Экологические проблемы загрязнения воздуха крупных городов.docx

• Влияние и значение татуировок в молодежной среде.docx