История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2020-12-27 | 269 |
5.00
из
|
Заказать работу |
|
|
· пусть требуется найти самую длинную цепочку символов С (или каких-то других, в соответствии с заданием) в символьной строке 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 кончилась
· проверим правильность работы алгоритма в особых случаях:
а) если вся строка состоит из букв C, значение переменной cLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;
б) если в строке нет символов 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] такой же, как и предыдущий, цепочка одинаковых символов продолжается, и нужно увеличить значение переменной cu r Len; если значение cu r Len стало больше maxLen, обновляем maxLen и запоминаем новый базовый символ в переменной c:
if s[i] == s[i-1]: # цепочка продолжается
curLen += 1 # увеличиваем длину
if curLen > maxLen: # если цепочка побила рекорд
maxLen = curLen # запоминаем её длину...
c = s [ i ] # и образующий символ
Else:
curLen = 1 # началась новая цепочка
если очередной символ не совпал с предыдущим, началась новая цепочка, и её длина пока равна 1 (это значение записывается в переменную cu r Len)
· получается такой цикл обработки строки:
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
· проверим правильность работы алгоритма в особых случаях:
в) если вся строка состоит из одинаковых символов, значение переменной curLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;
|
г) если в строке нет пар одинаковых символов, переменная curLen всегда равна 1, такое же значение будет и в переменной maxLen
Пример задания:
Р-07 (демо-2021). Текстовый файл 24.txt состоит не более чем из 106 символов 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) программа на Паскале:
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!