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

Определить количество максимальных элементов в массиве. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти число элементов массива, которые больше своих “соседей” http://www.cyberforum.ru/cpp-beginners/thread345621.html
Найти число элементов массива, которые больше своих “соседей”, т.е. предшествующего и последующего элементов.
C++ Математически описанный алгоритм -> C++ Имеется статья с алгоритмом. В С++ я новичок потому не очень понятно, как все же описать математические термины(см.картинку) и как сделать пересечение множеств(предполагалось использование библ. boost). Кто-нибудь уже сталкивался с написанием алгоритма по научным статьям? http://narod.ru/disk/23000238001/Local%20Optimality%20and%20Its%20Application%20k-claw%20free%20gr.pdf.html http://www.cyberforum.ru/cpp-beginners/thread345593.html
C++ Как тут происходит перестановка байтов...
Вот в книге Шилдта 4-е издание... есть такой пример: #include <iostream> #include <cstdio> #include <cstring> #include <windows.h> using namespace std; union swap_byte
Проблема в стэке C++
Всем Привет! Я делал упражнение на тему стэков, вроде всё сделал, но вылетает какая-то глупая ошибка. Вот код, я думаю, можно не объяснять, что должна делать программа, но если потребуется, объясню. Заголовочный файл с классом: // файл attach.h struct customer { char fullname; double payment; }; typedef customer Item;
C++ Список, стек и очередь. http://www.cyberforum.ru/cpp-beginners/thread345534.html
Файл содержит вещественные числа. Нужно удвоит вхождение всех чисел N. Решить с помощью стека, списка и очереди в С++. Вся информация считывается и выводится в файл, из консоли ничего не считывается и не выводится. Доступ к элементам стека или очереди происходит только с помощью функции извленения элемента из стека или очереди. Помогите пожалуйста!
C++ Возведение в степень n с помощью рекурсии #include<iostream> using namespace std; int funk(int,int); int main () {setlocale(LC_ALL,"Rus"); int a=2,n=5; cout<<funk(a,n); cin.get(); cin.get(); return 0; подробнее

Показать сообщение отдельно
Сыроежка
Заблокирован
31.08.2011, 19:17     Определить количество максимальных элементов в массиве.
К сожалению мой код никто, видимо, не запускал, а он содержит пропуск функционала. То есть должно быть не

C++
1
2
        std::pair<std::vector<int>::iterator, std::vector<int>::iterator> maxs = 
                std::equal_range(vec.begin(), vec.end(), *v.begin() );
а

C++
1
2
        std::pair<std::vector<int>::iterator, std::vector<int>::iterator> maxs = 
                std::equal_range(vec.begin(), vec.end(), *v.begin(), std::greater<int>() );
То есть нужен вызов этого алгоритма с предикатом.


Чтобы корректно написать код на основе этой идеи, то на самом деле можно обойтись без сортировки в убывающем порядке, чтобы найти максимум. Просто для поиска максимума можно воспользоваться обратными итераторами.

Вот как будет выглядеть код

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
int main()
{
        std::vector<int> vec((std::istream_iterator<int>(std::cin)), std::istream_iterator<int>());
        if ( vec.empty() )
        {
                std::cerr << "Error. Empty sequence" << std::endl;
                return 1;
        }
 
        std::sort(vec.begin(), vec.end(), std::greater<int>() );
 
        // Подсчет числа минимальных элементов
        std::pair<std::vector<int>::iterator, std::vector<int>::iterator> mins = 
                std::equal_range(vec.begin(), vec.end(), *v.begin() );
        std::cout << std::distance(mins.first, mins.second) << std::endl;
 
        // Подсчет числа максимальных элементов
        std::pair<std::vector<int>::reverse_iterator, std::vector<int>::reverse_iterator> maxs = 
                std::equal_range(vec.rbegin(), vec.rend(), *v.rbegin(), std::greater<int>() );
        std::cout << std::distance(maxs.first, maxs.second) << std::endl;
 
        return 0;
}
Но и это еще не все! На самом деле вместо алгоритмов std::equal_range проще пользоваться алгоритмом std::find_if, так как мы уже знаем, что последовательность упорядочена. Более того, эти алгоритмы в данном случае будут более эффективны, так как в противоположность им алгоритмы std::equal_range не принимают во внимание, что искомый элемент является первым (последним) в последовательности, и начинают его искать с помощью метода двоичного поиска.

Поэтому в вышеприведенном коде следует заменить алгоритмы std::equal_range на следующие предложения

C++
1
std::vector<int>::iterator it_min = std::find_if( vec.begin(), vec.end(), std::bind2nd( std::not_equal_to<int>(), *vec.begin() ) );
и

C++
1
std::vector<int>::reverse_iterator it_max = std::find_if( vec.rbegin(), vec.rend(), std::bind2nd( std::not_equal_to<int>(), *vec.rbegin() );
Соответственно и использовать функцию std::distance надо следующим образом

C++
1
std::distance( vec.begin(), it_min );
и

C++
1
std::distance( vec.rbegin(), it_max );

Теперь будет интересно посмотреть, кто предложит самый эффективный алгоритм подсчета числа максимальных или минимальных элементов в контейнере, который содержит всего один элемент!.

Добавлено через 2 минуты
Цитата Сообщение от easybudda Посмотреть сообщение
Кстати да, прав Сыроежка. В принципе если эту строчку заменить, то и не важно, что max не инициализирована.
Здесь также следует обратить внимание, что используется оператора >, тогда как для элементов контейнера требуется определение оператора <, а не >. То есть со многими определенными пользователем типами алгоритм не будет работать, так как пользователи не видят необходимости определять оператор >.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru