Сообщений в теме: 10

[chainyk]

Короче, столкнулся вот с такой задачкой:
Необходимо найти К-ый элемент в неупорядоченной последовательности целых чисел (в массиве, короче), при этом ограничение памяти 32 мб, а время работы программы линейное.
Люди кто учится на программистов, вы наверно уже сталкивались, помагите, очень надо!
Заранее спасибо!

[Shirson]

Это, что, полные условия задачи?

(Если да, тогда
print a[k]
)

[ivasi]

http://school.belhos...?section=4,2,44

http://lalls.narod.r...i_AFANASEVA.pdf

[chainyk]

Это, что, полные условия задачи?

(Если да, тогда
print a[k]
)

Да нет, так не проканает! Здесь весь прикол состоит в том что время выполнения задачи линейное(это когда число доминирующих операций не должно привышать размера даных), если ты учился то должен знать что это. Вот щас еще гляну ссылки ivasi, может разберусь!

[Propovednik]

Это, что, полные условия задачи?

(Если да, тогда
print a[k]
)

Да нет, так не проканает! Здесь весь прикол состоит в том что время выполнения задачи линейное(это когда число доминирующих операций не должно привышать размера даных), если ты учился то должен знать что это. Вот щас еще гляну ссылки ivasi, может разберусь!

Shirson абсолютно прав. Грамотно сформулируй условие задачи. Может тебе все-таки надо какой-то поиск в неупорядоченном массиве?

[chainyk]

Все разобрался!!!!
Глянул ссылки ivasi, это именно то что мне надо было, СПАСИБО БОЛЬШОЕ!
Немного уточню условие задачи, необходимо найти К-ый по величине елемент в неупорядоченном массиве, но кол-во переборов должно быть равно log2N - 1. Если искать обычным методом то тогда кол-во переборов 2N - 2.
Здесь http://school.belhos...?section=4,2,44 все подробно обьесняется.
Спасибо всем кто отвечал!

[Shirson]

chainyk, первое, чему я научился, это правильная формулировка своих вопросов, если, конечно, есть необходимость получить правильные ответы.

[BIGGboss]

Все разобрался!!!!
Глянул ссылки ivasi, это именно то что мне надо было, СПАСИБО БОЛЬШОЕ!
Немного уточню условие задачи, необходимо найти К-ый по величине елемент в неупорядоченном массиве, но кол-во переборов должно быть равно log2N - 1. Если искать обычным методом то тогда кол-во переборов 2N - 2.
Здесь http://school.belhos...?section=4,2,44 все подробно обьесняется.
Спасибо всем кто отвечал!

log2N-1 это условие двоичного поиска в упорядоченном массиве. Массив у нас неупорядочен - значит его надо отсортировать для начала.

[chainyk]

chainyk, первое, чему я научился, это правильная формулировка своих вопросов, если, конечно, есть необходимость получить правильные ответы.

Что конкретно тебе не понятно? Найти катый по величине элемент, что здесь непонятного! Аллгоритм с помощью которого решается эта задача - "Медиана из медиан", что то вроде усовершенствоного аллгоритма Гора.

[icpc]

попробуйте посмотреть "Кормен, Лейзерсон, Ривест. Алгоритмы. Поиск k-й порядковой статистики за линейное время".
вкратце идея такова: используйте ranodimzed partition из quicksort'а и в зависимости от мощностей получившихся половинок двигайтесь вправо или влево. высота получившегося дерева рекурсии - O(log n), но поскольку на каждом шаге количество рассматриваемых элементов уменьшается приблизительно вдвое, суммарное время работы алгоритма будет линейным. если что не понятно, пишите в приват - помогу

Сообщение отредактировал icpc: 24.07.2006, 14:15:57

[Shirson]

Что конкретно тебе не понятно? Найти катый по величине элемент, что здесь непонятного! Аллгоритм с помощью которого решается эта задача - "Медиана из медиан", что то вроде усовершенствоного аллгоритма Гора.

Внимательно следите за руками:

Ответом на вопрос "Необходимо найти К-ый элемент в неупорядоченной последовательности целых чисел (в массиве, короче)" является print(a[k]).
Именно a[K] является К-атым элементом неупорядоченной последовательности, короче, массива. Это и есть ответ на твой вопрос.

А вот если ты ищешь индекс элемента, равного К, или еще какой загиб, то так и надо спрашивать.
Если ты спрашиваешь одно, а имеешь ввиду другое - ответить правильно достаточно трудно - телепатия не развита.