Форум программистов, компьютерный форум CyberForum.ru

Придумать алгоритм - C++

Восстановить пароль Регистрация
 
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
03.07.2012, 16:25     Придумать алгоритм #1
Есть такая задачка : в массиве из n элементов за время nlogn найти пару элементов , сумма которых равна k , или сказать , что такой нет .
Собственно , код мне не нужен (сам напишу) , помогите с алгоритмом . Я сам не могу ничего сообразить (разве что банальный перебор , но там сложность n^2)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
03.07.2012, 17:11     Придумать алгоритм #2
попоробуйте использовать дерево,каждый узел содержит число и алгоритм примерно такой:обращаюсь к элементу дерева,вычисляем какое число(k - наше число) нужно и ищем его в дереве
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
03.07.2012, 17:12     Придумать алгоритм #3
Была похожая задача, и мне интересно, было ли моё предложение стоящим.. Нужна подсказка Попробуйте реализовать, и если можно, напишите, хороший ли это алгоритм. Только его нужно немного модифицировать (т.к. массив один): сначала сортируем массив, делим его пополам, а затем выбираем средний элемент в каждой половине, и далее двигаемся по "серединкам", складывая числа.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
03.07.2012, 17:24     Придумать алгоритм #4
можно сначала отсортировать массив
это O(n*log(n))
потом для каждого элемента s попробовать найти элемент (k-s) бинарным поиском. Если нашли такой элемент, то все хорошо и досрочный выход из функции. Иначе говорим что такоей пары элементов нет
худшая оценка для этого O(n*log(n))
в сумме это тоже O(n*log(n))
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
03.07.2012, 18:13     Придумать алгоритм #5
sandye51, ну и если это поможет, двигаться скачками по полдиапазона массива По идее, должно ускорить, но интересно, так ли это.

найти элемент (k-s) бинарным поиском
А, так это и есть бинарный поиск?
Yandex
Объявления
03.07.2012, 18:13     Придумать алгоритм
Ответ Создать тему
Опции темы

Текущее время: 23:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru