Задание 24
Пример 1
Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз.
Для выполнения этого задания следует написать программу.
Теория
В данном виде задач необходимо считать текст из файла в строковую переменную и проанализировать ее на наличие определенной последовательности символов. Часто необходимо применить оптимальный алгоритм, т.к. размер файла довольно большой. Символы можно сравнивать между собой с помощью знаков ">" или меньше "<" ( а так же ">=" или "<="), причём это сравнение происходит в алфавитном порядке. Например, символ "B" будет больше, чем "A" и т.д. Желательно владеть методами работы со строками - поиск, замена, подсчет количества символов, разбиение строки, длина строки и др. Поиск возможно также выполнить с помощью регулярных выражений - это строка, задающая шаблон поиска подстрок в тексте. Одному шаблону может соответствовать много разных строчек. Термин «Регулярные выражения» является переводом английского словосочетания «Regular expressions».
Решение
Пример 1
1-й способ ("в лоб"). Считываем файл в строковую переменную s. Выводим общее количество символов в файле и количество символов 'T'. Далее, в цикле просматриваем всю строку, если встретился символ 'T', то считаем длину цепочки до 100-го символа 'T' с помощью вложенного цикла while, при достижении 100-го символа 'T' сравниваем длину получившейся цепочки с maxchain и если она длиннее, то она и будет maxchain. Алгоритм неудачный, т.к. символов 'T' очень много (9 миллионов из 10 миллионов символов). Программа работает, но очень долго! Для каждого символа 'T' проверяется не менее 100 символов далее. Результат будет 133. Программа (Python)
s = open('demo_2024_24.txt','r').read()
print(len(s))
print(s.count('T'))
maxchain = 0
for i in range(len(s)-100):
if s[i]=='T':
countT=1
k=i+1
while k<len(s) and countT<100:
if(s[k]=='T'):
countT+=1
k+=1
if countT==100:
maxchain=max(maxchain, k-i)
print(maxchain)
2-й способ (оптимизированный алгоритм). Считываем файл в строковую переменную s. Выводим общее количество символов в файле и количество символов 'T'. Далее, в цикле просматриваем всю строку, если встретился символ 'T', то добавляем позицию 'T' в строке в массив letterT. Проверяем его длину, должна совпасть с количеством символов 'T'. Затем, с помощью цикла по позициям символа 'T', считаем расстояние от текущего символа 'T' до символа отстоящего вправо на 100 позиций, сравниваем длину получившейся цепочки с maxchain и если она длиннее, то она и будет maxchain. Алгоритм намного быстрее 1-го способа. Результат будет 133. Программа (Python)
s = open('demo_2024_24.txt','r').read()
print(len(s))
#список позиций букв T
letterT = []
for i in range(len(s)):
if s[i]=='T':
letterT.append(i)
print(len(letterT))
print(s.count('T'))
#максимальная цепочка символов со 100 'T'
maxchain = 0
for i in range(len(letterT)-100):
maxchain = max(maxchain, letterT[i+100]-letterT[i])
print(maxchain)
Ответ
Пример 1
133 (Время не более 20 минут)