Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Adastraz
7 / 7 / 0
Регистрация: 27.11.2013
Сообщений: 95
1

Алгоритм о сумме двух чисел в массиве

22.01.2015, 01:50. Просмотров 1530. Ответов 14
Метки нет (Все метки)

Доброго времени суток

Алгоритм должен получать на вход массив чисел, число и сообщать, есть ли в массиве пара чисел, сумма которых равна данному числу. Кажется тривиальным, но как его реализовать за ~ const * n * log(n) шагов.

Полагаю n потратить на сортировку, а дальше двоичные действия...
Какие идеи? Хочу потом реализовать на ЯП
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2015, 01:50
Ответы с готовыми решениями:

Алгоритм поиска количества простых чисел в заданном массиве
алгоритм поиск количества простых чисел в заданном целочисленном массиве из 50 элементов. Помогите...

Алгоритм произведения двух сортированных векторов сортированный картежей чисел
Добрый день. Мне ни как не удается написать удобоваримый алгоритм для следующей задачи: 1. На...

Постройте программу машины Поста, реализующей алгоритм сложения двух чисел
Постройте программу машины Поста, реализующей алгоритм сложения двух чисел, записанных на...

Нужно составить алгоритм суммирования двух байтных чисел в форме с фиксированной точкой.
Нужно разработать алгоритм суммирования двух байтных чисел в форме с фиксированной точкой... ...

Вывести сумму двух первых чисел одномерного массива, равную сумме двух последних чисел
Дан массив (одномерный) четырёхзначных чисел, вывести сумму двух первых чисел, равных сумме двум...

14
S_el
2311 / 1738 / 369
Регистрация: 15.12.2013
Сообщений: 7,023
22.01.2015, 01:55 2
Цитата Сообщение от Adastraz Посмотреть сообщение
Полагаю n потратить на сортировку,
Это чем вы хотите сортировать?
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
22.01.2015, 02:53 3
Кидаем все числа в map<int, int> MAP - мапа из числа в количество его вхождений. Дальше перебираем первое число, вычисляем, какое должно быть второе число и смотрим, что он есть в мапе в нужном количестве.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
22.01.2015, 10:07 4
Sort и бинпоиск разности (если разност равна первому числу, то просто проверить следующий элемент).
1
22.01.2015, 10:07
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
22.01.2015, 15:42 5
это весьма известная задача на "два указателя". поищите, в сети наверняка есть описание.
1
rocknrolla1
Заблокирован
27.01.2015, 00:00 6
SlavaSSU, думаю, ограничения на память тоже вводится. map-ами и подобными структурами данных редко пользуются в таких задачах, на то они и алгоритмические, чтоб сами думали, а не деревья внутри все делали.
К тому же, при работе с map, мы на вставку всех элементов и потратим nlog(n) операций - уже плохо, а еще искать нужно.
Как было правильно замечено товарищем salam, нужно использовать метод "бегунка".
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
27.01.2015, 01:34 7
rocknrolla1, 1) чет я не верю что там мапа не поместится. память обчыно ставят 64 Мб минимум.

насчет вставлять долго. если чать кода работает n * log(n), то неважно, сколько работает первая часть.

эта задача не на то, чтобы придумать решение без структур данных. эта задача на то, чтобы придумать НЕКВАДРАТНОЕ решение.
Такими структурами данных (vector, set, map...) часто пользуются в таких задачах.
0
rocknrolla1
Заблокирован
27.01.2015, 16:45 8
SlavaSSU, согласен, что O(nlogn) + O(n) = O(nlogn), где O(n) - вычисления после заполнения. Но заполнить нужно правильно еще, что не означает, что это возможно за ту минимальную сложность.
А насчет используемых структур, то пользуются обычно простыми массивами, без stl, если мы об олимпиадном программировании говорим.
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
27.01.2015, 17:54 9
rocknrolla1, ну vector, set, map, stack, queue - частенько.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
27.01.2015, 23:33 10
Цитата Сообщение от rocknrolla1 Посмотреть сообщение
А насчет используемых структур, то пользуются обычно простыми массивами, без stl, если мы об олимпиадном программировании говорим.
Нет. Как раз-таки stl'ем пользуются активно.
0
rocknrolla1
Заблокирован
27.01.2015, 23:44 11
Qwertiy, Да ладно, активно?! Вектор и строки не будем считать, т.к. это обыденность. Хотите сказать, что и алгоритмы <algorithm> еще используют? Если будет что-нибудь на графы, то очередь для Дейкстры, да и она не очень подходит, т.к. лучше кучу использовать, ну да ладно.
За примером далеко ходить не нужно, зайдите на codeforces.ru и посмотрите попытки участников - все руками пишется почти ( ну процентов 70% всех отправок точно ), так что об активности я бы не был так уверен.
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
28.01.2015, 00:23 12
vector, map, set, string, queue, stack - да.
multiset, deque - редко.
Из алгоритмов: sort, reverse, unique. Редко nth_element и binary_search.
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
28.01.2015, 03:40 13
rocknrolla1, для Дейкстры используют set или priority_queue.
Из алгоритмов cразу приходит в голову - sort, reverse, lower/upper_bound,
0
rocknrolla1
Заблокирован
28.01.2015, 16:57 14
SlavaSSU, priority_queue - это и есть куча, скорее всего, в реализации stl, как я и писал.
0
4ik
5 / 5 / 1
Регистрация: 05.02.2013
Сообщений: 96
03.02.2015, 23:13 15
Мб как-то так? Только я не помню индекс как я считал тут с 0 или с 1.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool find(int *W,int x,int r,int l,int ind)
{
    int m=(l+r)/2;
 
    if (m==r || m==l) return false;
    else if (W[ind]+W[m]<x) find(W,x,r,m,ind);
    else if (W[ind]+W[m]>x) find(W,x,m,l,ind);
    else return true;
}
 
bool sum(int *W,int x,int r)
{
    for (int i=0;i<r-1;i++)
        if (find(W,x,r,i,i))
            return true;
 
    return false;
}
0
03.02.2015, 23:13
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2015, 23:13

Среди чисел найти все, у которых сумма первых двух равна сумме последних двух
Помогите пожалуйста решить задание: среди четырехзначных чисел из интервала, заданного...

Из чисел вывести такие, в которых сумма двух левых цифр является чётным числом и равным сумме двух правых цифр
Помогите составить программу с помощью qbasic Из четырёхзначных чисел ( Целых по значению...

Получить цифры числа равного сумме цифр двух чисел
даны цифры двух целых чисел : двузначного а2а1 и однозначного b,где а1-число единиц,а2-число...


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

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

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