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

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

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

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

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

Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 20:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза (C++):

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

Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза Матрица: 2 4 7 6 5 8 9 34 43 4 34 53 45 345 3 6 5 56...

Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы - C++
Ребята..помогите,пожалуйста.Надо решить задачу,а никак не выходит(даже не знаю..прочитала в книге все про указатели и не пойму как...

Максимальное из чисел встречающихся в заданной матрице более одного раза - C++
Есть программа, она работает, но мне не понятен принцип, мог бы кто нибудь помочь? #include "stdafx.h" #include <iostream> ...

Максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
//Дана целочисленная прямоугольная матрица. Определить: //1) количество строк, не содержащих ни одного нулевого элемента; ...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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++
4225 / 2199 / 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++
4225 / 2199 / 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++
4225 / 2199 / 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++
4225 / 2199 / 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++
4225 / 2199 / 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 Посмотреть сообщение
Все равно непрозрачный алгоритм, можете хоть на псевдокоде написать.
Я подумал получше и понял, что не прав. Не работает такой алгоритм.)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 09:49
Привет! Вот еще темы с ответами:

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
максимальное из чисел, встречающихся в заданной матрице более одного раза. Добрый вечер, есть программка, все компил., но после...

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Дана целочисленная прямоугольная матрица.Определить: Максимальное из чисел, встречающихся в заданной матрице более одного раза ...

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Здравствуйте!Помогите пожалуйста решить задачу. Дана целочисленная матрица. Определить максимальное из чисел, встречающихся в заданной...

Найти максимальное число из, встречающихся в матрице более одного раза - C++
Хей. Есть рабочая программа, но для её полной правильности в ней нужно использовать Функцию или процедуру. Задание: Найти максимальное...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.10.2011, 09:49
Ответ Создать тему
Опции темы

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