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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
#1

Алгоритм поиска одинаковых элементов - C++

20.07.2013, 18:47. Просмотров 1957. Ответов 9
Метки нет (Все метки)

Подскажите какой-нибудть алгоритм (реализацию писать не надо)

Есть числовые записи в файле
грубо говоря

1 4 6 8
3 5 14 27
1 2 4 6 17
3 5 6 14

Нужен алгоритм который найдет все пары одинаковых чисел во всех записях
т.е в данном случае у первой записи и у 2 ой - нету пар, у первой и 3-ей 1 - 4 - 6 и тд....
Сложность не более O(N2)...

Подскажите в сторону чего смотреть....
Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.07.2013, 18:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм поиска одинаковых элементов (C++):

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

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

Замена первой группы одинаковых элементов на последнюю группу одинаковых элементов - C++
Всем привет, помогите с заменой первой группы одинаковых элементов в нашем случае пять единиц на последнюю группу одинаковых элементов,...

Составить алгоритм и программу длля поиска в массиве целых чисел из 5 элементов минимального числа. - C++
Составить алгоритм и программу длля поиска в массиве целых чисел из 5 элементов минимального числа.

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Написать программу поиска двух одинаковых подряд идущих символа в файле - C++
помогите пожалуйста!! напишите программу которая принимает с клавиатуры название файла и выводит на экран "Есть", если в файле...

9
vxg
Модератор
3188 / 1991 / 228
Регистрация: 13.01.2012
Сообщений: 7,712
20.07.2013, 19:08 #2
1 заводим массив списков номеров записей содержащий столько элементов сколько у нас может быть цифр (как вариант - в начале проходим по всем записям и ищем максимальное число)
2 проходим по всем записям и кладем номер записи в список под номером цифры
3 очевидно, что все возможные сочетания в пределах каждого списка являются всеми возможными парами
1
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
20.07.2013, 19:35  [ТС] #3
не понял второй пункт..., а именно "кладем номер записи в список под номером цифры"
читаем файл - первая запись 1 4 6 8 и ???.... номер записи один (ну или 0 если списки записей в массиве)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
20.07.2013, 19:44 #4
Dark2013, если можно юзать сложность O(n^2), то просто проходи по всем числам со всем записей цикл в цикле как-то так:
C++
1
2
for (int i = 0; i<n; ++i)
   for (int j = 0; j<n; ++j)
И ищи пару числу A[i] (где A - число с номером i в последовательности, которую можно получить, если записать все записи подряд)

Добавлено через 1 минуту
Dark2013, vxg вероятно хотел сказать, что, если известно минимальное и максимальное числа, которые могут быть в записях, то просто можно создать массив списков A, в котором A[i] будет означать список позиций, в которых встретилось число i. Основываясь на этих списках и можно вывести все пары.
1
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
20.07.2013, 19:55  [ТС] #5
ага)) Это ты найдеш только для одной записи....а тебе нужно для всех....
- добавляй еще один цикл - получится полный перебор O(N3)

вроде начинаю врубаться... ща запилю
0
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.07.2013, 22:17 #6
Цитата Сообщение от Dark2013 Посмотреть сообщение
Сложность не более O(N2)...
А N это что? число всех элементов? Тогда трудно придумать что-то, что превысит O(N^2). Вот если бы условие стояло: сложность не выше O(N ln N) или даже не выше линейной, тогда - другое дело.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
20.07.2013, 23:43 #7
Цитата Сообщение от Dark2013 Посмотреть сообщение
- добавляй еще один цикл - получится полный перебор O(N3)
куда еще 1 цикл? В моем алго N - кол-во элементов во всех записях. Я подразумеваю, что ты думаешь это:
C++
1
2
for (int l = 0; l<xx; ++l) //выбираем номер списка
    for (int i = 0; i<length[xx]; ++i) //перебираем числа в списке
От добавления этого сложность не изменится: мы просто проходим по всем элементам. Есть двумерный массив из 3 столбцов и 5 строк - итого 15 элементов и есть обычный линейный массив из 15 элементов. По твоей логике, чтобы пройтись по элементам одномерного массива я могу за линейное время, а по двумерному - за квадрат?
1
vxg
Модератор
3188 / 1991 / 228
Регистрация: 13.01.2012
Сообщений: 7,712
21.07.2013, 08:22 #8
Цитата Сообщение от Dani Посмотреть сообщение
vxg вероятно хотел сказать, что, если известно минимальное и максимальное числа, которые могут быть в записях, то просто можно создать массив списков A, в котором A[i] будет означать список позиций, в которых встретилось число i. Основываясь на этих списках и можно вывести все пары.
точно. именно так. причем сложность будет никакой - нужно просто один раз пройти все записи (или если минимум и максимум не известные три раза). после этого вывод всех возможных сочетаний - механическая операция сложность которой, наверное, можно не включать в общую сложность алгоритма
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
21.07.2013, 08:22 #9
у вас случайно числа в записях упорядочены?
1
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 08:34 #10
Цитата Сообщение от salam Посмотреть сообщение
у вас случайно числа в записях упорядочены?

Не по теме:

вот и я намекаю, что при определенном раскладе сложность гораздо меньше будет



Цитата Сообщение от Dani Посмотреть сообщение
C++
1
2
for (int l = 0; l<xx; ++l) //выбираем номер списка
    for (int i = 0; i<length[xx]; ++i) //перебираем числа в списке
по условию задачи, надо перебирать числа во всех предыдущих списках (поэтому три цикла), судя по примеру, но от этого сложность алгоритма не меняется.
0
21.07.2013, 08:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.07.2013, 08:34
Привет! Вот еще темы с ответами:

Алгоритм поиска А* - C++
Помогите написать код на с++,реализирующий алгоритм поиска А*, пожалуйста. ...

Алгоритм поиска - C++
есть ли в STL алгоритм принимающий упорядоченный интервал и проверяющий, содержит ли данный интервал последовательность из N элементов,...

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

Алгоритм поиска пути A* - C++
использую библиотеку SFML только для окна пытался сделать алгоритм поиска пути от одной до другой точки(левая и правая кнопка мыши) окно...


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

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

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