Волнистая последовательность |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Волнистая последовательность |
xprogrammer |
Сообщение
#1
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
Назовенм последовательность волнистой если для всех кроме первого элемента выполняется: для всех элементов кроме первого и последнего, что либо этот член последовательности больше всех своих соседей, либо меньше.
Например : 12121212121-волнистая а 123321 - нет дана последовательность и надо из неё выделить самую большую волнистую подпоследовательность . Последовательность храниться в массиве помогите хоть алгоритмом. |
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Идем слева направо по последовательности, и помним, сколько (максимум) последних прочитанных символов удовлетворяют условию "волнистости". А именно:
1. Один символ всегда волнистый. 2. Два символа, только если они не равны, волнистые. 3. n+1 символов - волнистые, если первые n из них - волнистые, и для n-го символа выполняется условие "больше всех своих соседей, либо меньше" Получается алгоритм: 1. Прочитать следующий символ. Считать его первым в искомой подстроке (ПИП) 2. Прочитать следующий символ. Если он равен ПИП, считать его ПИПом и перейти к шагу 2 3. Иначе считать его вторым в искомой подстроке (ВИП). Найден ответ длины 2. 4. Прочитать следующий символ. Если он равен предыдущему прочитанному, считать его ПИПом и перейти к шагу 2 5. Проверить для предыдущего символа (стоящего перед только что прочитанным) условие волнистости. Если оно выполняется, перейти к шагу 4. 6. Иначе запомнить найденный ответ (не включая последний прочитанный символ). Последних два прочитанных символа считать ПИПом и ВИПом соответственно, и перейти к шагу 4. При этом "запомнить найденный ответ" означает не вырезать саму подстроку (подмассив), а просто запомнить индексы первого (ПИП) и последнего элементов в подпоследовательности. Алгоритм получается линейный. |
Текстовая версия | 8.05.2024 11:44 |