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

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

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

Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза - C++

03.10.2011, 20:00. Просмотров 7312. Ответов 46
Метки нет (Все метки)

Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 20:00     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Посмотрите здесь:
Найти максимальное из чисел встречающихся в массиве более одного раза C++
C++ Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы C++
Максимальное из чисел встречающихся в заданной матрице более одного раза C++
C++ Максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 09:55     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #16
Deviaphan, просто я математически доказал, что сложность алгоритма эквивалентна сложности сортировки, вот и удивился
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 10:03     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #17
Цитата Сообщение от Thinker Посмотреть сообщение
я математически доказал, что сложность алгоритма эквивалентна сложности сортировки
Я придумал работающий (на этот раз) алгоритм, но требуется дополнительная память. Причём ОЧЕНЬ много её требуется, в соответствии с разрядностью чисел. Зато, линейная сложность.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 10:08     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #18
Цитата Сообщение от Deviaphan Посмотреть сообщение
Сложность алгоритма и время его выполнения связаны очень слабо. Т.е. алгоритм с меньшей сложностью может работать дольше, чем алгоритм с большей сложностью.
Что верно, то верно. Имеется в виду сложность алгоритма, зависящая от размера массива с асимптотикой и O-большим.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 10:46     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #19
Добавлю, что
http://www.cyberforum.ru/cgi-bin/latex.cgi?\lim_{n \rightarrow \infty}\frac{ln n}{n}=0
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:45     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #20
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 11:48     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #21
Цитата Сообщение от romex Посмотреть сообщение
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:50     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #22
Цитата Сообщение от romex Посмотреть сообщение
Что-то не могу придумать алгоритм с линейной сложностью + доп память.
Для чисел в диапазоне [0-255]
C++
1
2
3
4
5
6
7
8
9
10
11
12
int count[256] = {0};
//массив a[100]
for( int i = 0; i < 100; ++i )
   cout[ a[i] ]++;
 
int maxValue = -1;
for(int i = 255; i >=0; --i)
    if( count[i] > 1 )
    {
         maxValue = i;
         break;
    }
Соответственно, для отрицательных чисел нужно делать корректировку. И объём дополнительной памяти равен разрядности искомых чисел. В данном случае 8 бит.
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:56     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #23
А для вещественных чисел?

Добавлено через 1 минуту
Все, до меня дошло, спасибо...
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 11:57     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #24
Цитата Сообщение от romex Посмотреть сообщение
А для вещественных чисел?
Закодировать их с помощью биекции целыми числами, поэтому и говорю о БОЛЬШОЙ памяти. Если диапазона целых чисел не хватит, то использовать n-мерные кольца вычетов (вернее, модули) и поразрядную сортировку.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:58     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #25
Цитата Сообщение от romex Посмотреть сообщение
А для вещественных чисел?
C++
1
2
3
float f;
int count[0xFFFFFFFF] = {0};
count[*(UINT*)(&f)]++;

Шутка юмора
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:59     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #26
В этом случае дополнительная память конечно превышает размер исх данных, но не на много...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:59     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #27
Но возникнут проблемы с погрешностью.(
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:01     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #28
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но возникнут проблемы с погрешностью.(
Разбить на целые и дробные части, а далее поразрядная сортировка.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
04.10.2011, 12:02     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #29
Цитата Сообщение от Thinker Посмотреть сообщение
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Цитата Сообщение от Thinker Посмотреть сообщение
а далее поразрядная сортировка.
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 12:04     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Еще ссылки по теме:
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное число из, встречающихся в матрице более одного раза C++
C++ найти максимальное из чисел, встречающееся в заданном целочисленном массиве более одного раза
C++ Дана произвольная матрица, определить: Максимальное из чисел, встречающихся в заданной матрице более одного раза

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:04     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #30
Цитата Сообщение от fasked Посмотреть сообщение
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Ну о безграничных типах мы не говорим.
Yandex
Объявления
04.10.2011, 12:04     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Ответ Создать тему
Опции темы

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