Волнистая последовательность |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Волнистая последовательность |
xprogrammer |
Сообщение
#1
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
Назовенм последовательность волнистой если для всех кроме первого элемента выполняется: для всех элементов кроме первого и последнего, что либо этот член последовательности больше всех своих соседей, либо меньше.
Например : 12121212121-волнистая а 123321 - нет дана последовательность и надо из неё выделить самую большую волнистую подпоследовательность . Последовательность храниться в массиве помогите хоть алгоритмом. |
xprogrammer |
Сообщение
#2
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
нет, вы неправильно мепня поняяли. Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn
Например: Xn : 1 2 3 4 5 6 7 8 9 0 Yn : 1 3 5 7 9 |
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn О, вот это уже поинтереснее Считаем, что в массиве все числа - от 0 до n-1. Если это не так, то понятно, что можно построить биекцию. Введем понятие верхних и нижних волнистых подпоследовательностей. Верхней называем такую, у которой последнее число *больше* предпоследнего, нижней - такую, у которой последнее число *меньше* предпоследнего. Подпоследовательности длины 0 и 1 являются и верхними, и нижними одновременно. Заведем два массива: А[0 .. n-1] и В[0 .. n-1]. Изначально A[i] = B[i] = 0 для всех i. Идем слева направо по входному массиву (напомню, что все числа в нем - от 0 до n-1). После прочтения каждого числа состояние массивов А и В должно быть таким: A[i] - длина максимальной волнистой верхней подпоследовательности в прочитанном куске, оканчивающейся числом i, B[i] - длина максимальной волнистой нижней подпоследовательности в прочитанном куске, оканчивающейся числом i. В начале все A[i] = B[i] = 0, потому что еще ничего не прочитано. Теперь, пусть мы прочли число x. В результате могут поменяться только значения A[x] и B[x]. Они станут равны: A[x] = max(B[0], B[1], B[2], .., B[x-1]) + 1 B[x] = max(A[x+1], A[x+2], A[x+3], .. , A[n - 1]) + 1 Действительно, чтобы с помощью х получить наилучшую верхнюю подпоследовательность, нужно приписать х к наилучшей из найденных нижних подпоследовательностей, оканчивающихся числами, меньшими х. И наоборот. Пройдя слева направо по всему входному массиву, мы заполним постепенно массивы А и В. Теперь наибольшему из всех чисел в А и В соответствует самая длинная волнистая подпоследовательность. Как ее теперь построить - додумаешь сам. Вот. Это решение очень легко пишется, и работает за квадрат. Если тебе надо за n log n, разберись с этим, и приходи |
Текстовая версия | 20.04.2024 22:40 |