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