Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
dota
3 / 3 / 0
Регистрация: 20.09.2010
Сообщений: 100
#1

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

03.07.2012, 16:25. Просмотров 675. Ответов 4
Метки нет (Все метки)

Есть такая задачка : в массиве из n элементов за время nlogn найти пару элементов , сумма которых равна k , или сказать , что такой нет .
Собственно , код мне не нужен (сам напишу) , помогите с алгоритмом . Я сам не могу ничего сообразить (разве что банальный перебор , но там сложность n^2)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 16:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Придумать алгоритм (C++):

Не могу придумать алгоритм - C++
В общем у меня есть переменные left = 'n'; top = 'n'; right = 'y'; down = 'y'; и нужно чтоб функция выбирала рандомно одну из...

Придумать алгоритм вычисления квадратного корня, не использую функции возведения в степень - C++
Необходимо придумать алгоритм, вычисления квадратного корня, не использую функции возведения в степень и соответственно саму функцию...

необходимо каким-то образом пронумеровать все сочетания, никак не могу придумать алгоритм - C++
Мне необходимо каким-то образом пронумеровать все сочетания, никак не могу придумать алгоритм. Например из 10 по 5 = 252, если нумеровать...

Придумать формулу/алгоритм, который будет определять в какой из пяти корзин расположен шарик - C++
Доброго времени суток. Помогите придумать формулу/алгоритм, который будет определять в какой из пяти корзин расположен шарик. Шарики...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

придумать функцию))) - C++
Помогите пожалуйсто придумать функцию, реализирующие те же действия что и char*strcpy

4
alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
03.07.2012, 17:11 #2
попоробуйте использовать дерево,каждый узел содержит число и алгоритм примерно такой:обращаюсь к элементу дерева,вычисляем какое число(k - наше число) нужно и ищем его в дереве
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
03.07.2012, 17:12 #3
Была похожая задача, и мне интересно, было ли моё предложение стоящим.. Нужна подсказка Попробуйте реализовать, и если можно, напишите, хороший ли это алгоритм. Только его нужно немного модифицировать (т.к. массив один): сначала сортируем массив, делим его пополам, а затем выбираем средний элемент в каждой половине, и далее двигаемся по "серединкам", складывая числа.
0
sandye51
программист С++
687 / 589 / 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))
3
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
03.07.2012, 18:13 #5
sandye51, ну и если это поможет, двигаться скачками по полдиапазона массива По идее, должно ускорить, но интересно, так ли это.

найти элемент (k-s) бинарным поиском
А, так это и есть бинарный поиск?
0
03.07.2012, 18:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 18:13
Привет! Вот еще темы с ответами:

Придумать условие - C++
выводит числа двоичная запись которых представляет собой симметричную последовательность нулей и единиц (начинающуюся единицей!). В...

Придумать обьектную область - C++
В общем дали задание придумать полезную программу в какой-то области и описать для этой области 5-6 обьектов. Сложность для меня...

Придумать свою кодировку файла - C++
Добрый день. Понятия не имею, как это сделать. Подскажите, пожалуйста. Пусть есть текстовый файл некоторого размера. Придумать свою...

Придумать тему для курсовой.. - C++
Ну в общем все сказано в названии этой темы. Тема должна быть актуальной) Программа любого вида, на любом языке. Программа может быть...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru