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

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

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

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

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

Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 20:00     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Посмотрите здесь:
Найти максимальное из чисел встречающихся в массиве более одного раза C++
C++ Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы C++
Максимальное из чисел встречающихся в заданной матрице более одного раза C++
C++ Максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
03.10.2011, 20:21     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #2
Код
1) Присваиваете переменной max минимальное значение для ее типа. 
2) Пробегаете двойным циклом по массиву. 
3) if(arr[i] == arr[j])
    {
        if(arr[i] > max)
            max = arr[i]
        break;//переходите на следующую итерацию цикла i
    }
4) После циклов ставите условие на max, если max == минимальному значению для типа 
переменной max, то все числа входят в массив только единожды, иначе выводите max 
По хорошему надо вообще переменную bool, чтобы отслеживать изменения max, поскольку если в 
массиве будут только элементы, равные минимальному допустимому значению для типа max, тогда 
программа выдаст, что максимальных повторяющихся элементов нет.
Ну вот, вроде так должно получиться, может есть получше способ?

Добавлено через 3 минуты

Не по теме:

Запомните, а лучше запишите. Плодить темы на форуме "не есть хорошо"

Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
03.10.2011, 20:41     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #3
Цитата Сообщение от soon Посмотреть сообщение
может есть получше способ?
Разумеется есть. Отсортировать массив и с конца начать искать двойное вхождение.
soon
03.10.2011, 21:01
  #4

Не по теме:

Мда. Что-то о сортировке я даже и не подумал.

Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.10.2011, 23:25     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #5
Цитата Сообщение от Deviaphan Посмотреть сообщение
Разумеется есть. Отсортировать массив и с конца начать искать двойное вхождение.
Для произвольного случая сложность будет O(n*log n). Интересно, а еще оптимальнее можно.

Добавлено через 22 минуты
Цитата Сообщение от Thinker Посмотреть сообщение
Для произвольного случая сложность будет O(n*log n). Интересно, а еще оптимальнее можно.
Нет, нельзя, сложность данной задачи эквивалентна сложности сортировки
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 06:35     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #6

Нет, нельзя, сложность данной задачи эквивалентна сложности сортировки
Можно. За линейное время. Но нужно использовать дополнительный контейнер типа std::map.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 08:44     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Можно. За линейное время. Но нужно использовать дополнительный контейнер типа std::map.
Нельзя, задача эквивалентна сортировке, хоть можно и без нее обойтись, но сложность алгоритма та же будет. Контейнер тоже нельзя, а то просто будет слишком. Имеется ввиду написать алгоритм без использования дополнительной памяти, работать только с массивом.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 09:00     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #8
Цитата Сообщение от Thinker Посмотреть сообщение
Имеется ввиду написать алгоритм без использования дополнительной памяти, работать только с массивом.
В задании такого ограничения не указывается.)
Хотя, я не учёл сложность поиска значения в мапе. Т.е. всё равно близко к N*logN получается.
С сортировкой самый простой вариант.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 09:08     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
С сортировкой самый простой вариант.
Почти да. Если же элементы массива нельзя менять местами, то алгоритм поиска будет похож на сортировку.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
В задании такого ограничения не указывается.)
Просто задался сам для себя таким вопросом
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 09:15     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #10
Что-то я туплю вообще. За один проход решается задача, с использованием трёх дополнительных переменных.Одна для текущего максимального повторённого значения, одна для счётчика и одна для текущего максимального не повторённого значения.
Так что всё предельно просто.)

Добавлено через 53 секунды
Если количество повторений не важно, то и счётчик можно не использовать.
-=ЮрА=-
Заблокирован
Автор FAQ
04.10.2011, 09:26     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #11
Цитата Сообщение от bubajiex Посмотреть сообщение
Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
- ниже С++ реализация твоего алгоритма(никаких контейнеров, сортировок, макс элемент выбираем ещё при вводе)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <conio.h>
using namespace std;
 
int main()
{
    int *vec,i,j,n,maxv;
    do
    {
        std::cout<<"Enter num elemens : ";
        std::cin>>n;
        vec = new int[n];
        std::cout<<"Enter elements\r\n";
        //Однозначно меньше данного числа в массиве не встретим
        maxv = -INT_MAX;
        for(i = 0; i < n; i++)
        {
            std::cout<<"vec["<<i + 1<<"] = ";
            std::cin>>vec[i];
            //Запускаем пробор введенного массива
            //чтобы проверить присутствует ли в нём
            //vec[i] хотя бы раз
            for(j = 0; j < i; j++)
            {
                if(vec[j] == vec[i])
                {
                    if(maxv < vec[i])
                        maxv = vec[i];
                    break;//Если vec[j] == vec[i]
                    //выполнилось прекращаем поиск в уже введенном
                }
            }
        }
        std::cout<<"MAX element in vector sequences : "<<maxv<<"\r\n";
        delete [] vec;
    }
    while(toupper(getch()) == 'Y');
    return 0;
}
Миниатюры
Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза  
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 09:28     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #12
Цитата Сообщение от Deviaphan Посмотреть сообщение
За один проход решается задача
А начальные значения чем будете инициализировать?

Добавлено через 1 минуту
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- ниже С++ реализация твоего алгоритма(никаких контейнеров, сортировок)
Это и так было понятно. Вопрос как улучшить сложность алгоритма.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 09:32     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #13
Цитата Сообщение от Thinker Посмотреть сообщение
А начальные значения чем будете инициализировать?
Вместо значения буду хранить индекс элемента. Изначально -1.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 09:35     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #14
Цитата Сообщение от Deviaphan Посмотреть сообщение
Вместо значения буду хранить индекс элемента. Изначально -1.
Все равно непрозрачный алгоритм, можете хоть на псевдокоде написать.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 09:49     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #15
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
ниже С++ реализация твоего алгоритма
Алгоритм очень немного не корректен. Минимальное значение int != -INT_MAX. Т.е. существует вариант заполнения массива, при котором алгоритм вернёт не правильное значение.

Добавлено через 13 минут
Цитата Сообщение от Thinker Посмотреть сообщение
Все равно непрозрачный алгоритм, можете хоть на псевдокоде написать.
Я подумал получше и понял, что не прав. Не работает такой алгоритм.)
Thinker
Эксперт C++
4223 / 2197 / 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++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 10:08     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #18
Цитата Сообщение от Deviaphan Посмотреть сообщение
Сложность алгоритма и время его выполнения связаны очень слабо. Т.е. алгоритм с меньшей сложностью может работать дольше, чем алгоритм с большей сложностью.
Что верно, то верно. Имеется в виду сложность алгоритма, зависящая от размера массива с асимптотикой и O-большим.
Thinker
Эксперт C++
4223 / 2197 / 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 11:45     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Еще ссылки по теме:
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное число из, встречающихся в матрице более одного раза C++
C++ найти максимальное из чисел, встречающееся в заданном целочисленном массиве более одного раза
C++ Дана произвольная матрица, определить: Максимальное из чисел, встречающихся в заданной матрице более одного раза

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

Или воспользуйтесь поиском по форуму:
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:45     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #20
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
Yandex
Объявления
04.10.2011, 11:45     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Ответ Создать тему
Опции темы

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