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

@валентин777 · Регистрация: 01.06.2011

Студворк — интернет-сервис помощи студентам

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

@Сыроежка · 29.08.2011, 18:33

Сообщение от CyBOSSeR

Зачем здесь typedef?

По-моему, в этой теме первым появилось решение alex_x_x'а. Да и ничего сверхестественного в Вашем решении нет, я когда увидел эту тему сразу подумал о решении схожим с решением alex_x_x'а, так что ничего оригинального в Вашем подходе нет, чтобы так им кичиться.

А чего "сверхестественного" вы ждете?! Совершенно непонятно.
Что касается временной хронологии, то как раз первым здесь появилась моя ссылка на другую аналогичную тему, где был представлен мой алгоритм.

@easybudda · 29.08.2011, 19:11

Сообщение от Сыроежка

Мой код профессиональный

А мой - нет!

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
#include <stdio.h>
    
int * max_element(const int * arr, size_t size){
    return ( size < 2 ) ? (int*)arr : ( *arr < *(arr + size - 1) ) ? max_element(arr + 1, size - 1) : max_element(arr, size - 1);
}
 
size_t count(const int * arr, size_t size, int val){
    return ( size ) ? ( *arr == val ) + count(arr + 1, size - 1, val) : 0;
}
 
void dump(const int * arr, size_t size){
    while ( size-- )
        printf("%d%c", *arr++, ( size ) ? ' ' : '\n');
}
 
#define SIZE 10
 
int main(void){
    int arr[SIZE] = { 1, 3, 5, 3, 2, 5, 4, 3, 1, 2 }, me = *max_element(arr, SIZE);
    
    printf("Array: ");
    dump(arr, SIZE);
    printf("Max element %d meets %d times.\n", me, count(arr, SIZE, me));
    
    return 0;
}

Вот ещё до кучи...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
#include <algorithm>
#include <iterator>
    
int main(){
    const int size(10);
    int arr[size] = { 1, 3, 5, 3, 2, 5, 4, 3, 1, 2 };
    
    std::cout << "Array: ";
    std::copy(arr, arr + size, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    std::map<int, int> map;
    for ( int i = 0; i < size; ++i )
        map[arr[i]]++;
    std::cout << "Max element " << map.rbegin()->first << " meets " << map.rbegin()->second << " times." << std::endl;
    
    return 0;
}

@Сыроежка · 29.08.2011, 19:33

Сообщение от easybudda

А мой - нет!

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
#include <stdio.h>
    
int * max_element(const int * arr, size_t size){
    return ( size < 2 ) ? (int*)arr : ( *arr < *(arr + size - 1) ) ? max_element(arr + 1, size - 1) : max_element(arr, size - 1);
}
 
size_t count(const int * arr, size_t size, int val){
    return ( size ) ? ( *arr == val ) + count(arr + 1, size - 1, val) : 0;
}
 
void dump(const int * arr, size_t size){
    while ( size-- )
        printf("%d%c", *arr++, ( size ) ? ' ' : '\n');
}
 
#define SIZE 10
 
int main(void){
    int arr[SIZE] = { 1, 3, 5, 3, 2, 5, 4, 3, 1, 2 }, me = *max_element(arr, SIZE);
    
    printf("Array: ");
    dump(arr, SIZE);
    printf("Max element %d meets %d times.\n", me, count(arr, SIZE, me));
    
    return 0;
}

Можно было бы возвращаемое значение из функции max_element сделать таким же, как и параметр массива, то есть const int * и не далать приведение типов (int*)arr Так как нет большого смысла возвращать не константную ссылку, так как в вашем алгоритме нет определенности, какой именно максимальный элемент последовательности возвращается. То есть если бы вы могли гарантировать, что ваша функция возвращает первый максимальный элемент в последовательности, или напротив, самый последний, то тогда пользователь мог бы воспользоваться не константным указателем, так как он представляет, с каким именно элементом он имеет дело. А так - это гадание на кофейной гуще.

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

@easybudda · 29.08.2011, 19:41

Сообщение от Сыроежка

Так как нет большого смысла возвращать не константную ссылку, так как в вашем алгоритме нет определенности, какой именно максимальный элемент последовательности возвращается.

Наверное, с высоты профессионализма такие мелочи и не видны, но вообще-то в С функции, возвращающие константные значения - UB (не мне рассказывать Вам, профессионалу, что это значит). А определённость как раз есть - функция возвращает указатель (да-да, в С нет ссылок, не задалось как-то с ними) на ПЕРВЫЙ максимальный элемент. Вы своим профессиональным взглядом внимательнее присмотритесь.

@Сыроежка · 29.08.2011, 19:44

Сообщение от easybudda

Наверное, с высоты профессионализма такие мелочи и не видны, но вообще-то в С функции, возвращающие константные значения - UB (не мне рассказывать Вам, профессионалу, что это значит). А определённость как раз есть - функция возвращает указатель (да-да, в С нет ссылок, не задалось как-то с ними) на ПЕРВЫЙ максимальный элемент. Вы своим профессиональным взглядом внимательнее присмотритесь.

Да, я ошибся. В случае равенства у вас возвращается подмассив с исключением последнего элемента.

@Thinker · 29.08.2011, 19:53

Сообщение от Сыроежка

Да, я ошибся...

Не по теме:

Неужели это случилось-признание ошибки!:)

@CyBOSSeR · 29.08.2011, 20:37

Сообщение от Сыроежка

А чего "сверхестественного" вы ждете?! Совершенно непонятно.

В том то и дело, для чего упирать на профессионализм, если вы решили задачу очевидным способом? Чем Ваше, как вы зявляете, "профессиональное" решение отличается от решения ale_x_x, при условии что у Вас присутсвует совершенно ненужное поле?

Сообщение от Сыроежка

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

Первая ссылка на Ваше решение в посте #38, решение ale_x_x в #32.

@Сыроежка · 30.08.2011, 20:12

Сообщение от CyBOSSeR

В том то и дело, для чего упирать на профессионализм, если вы решили задачу очевидным способом? Чем Ваше, как вы зявляете, "профессиональное" решение отличается от решения ale_x_x, при условии что у Вас присутсвует совершенно ненужное поле?

Первая ссылка на Ваше решение в посте #38, решение ale_x_x в #32.

Спасибо, насмешили меня! Знаете, что такое профессионально написанный код? Это не тогда, как вы наивно думаете, задача решена не очевидным способом. К написанию кода это вообще никакого отношения не имеет, как вам лично это не покажется странным. Профессионально написанный код - это 1) грамотный, 2) корректный, 3) легко читаемый код. Более того он даже не обязан быть идеальным кодом!

Что касается ваших ссылок на посты, то я имел в виду хронологию, что алгоритм уже написан в ранее обсуждаемой аналогичной теме. То есть, фактически, происходило переписание ранее написанного алгоритма, да еще не совсем грамотно и с ошибками. Это я и имел в виду, что проще обратиться к той теме, а не переписывать заново некорректно уже написанный код. Иначе это похоже на испорченный граммофон.

@ForEveR · 30.08.2011, 20:34

Не оптимально) Но вариант.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
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;
    }
    int element = *std::max_element(vec.begin(), vec.end());
    std::sort(vec.begin(), vec.end());
    std::pair<std::vector<int>::iterator, std::vector<int>::iterator> maxs = 
        std::equal_range(vec.begin(), vec.end(), element);
    std::cout << std::distance(maxs.first, maxs.second) << std::endl;
    return 0;
}

@fasked · 30.08.2011, 20:38

Сообщение от ForEveR

Не оптимально

Особенно, если учесть то, сколько в последовательности может быть элементов

@Сыроежка · 30.08.2011, 20:40

Сообщение от ForEveR

Не оптимально) Но вариант.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
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;
    }
    int element = *std::max_element(vec.begin(), vec.end());
    std::sort(vec.begin(), vec.end());
    std::pair<std::vector<int>::iterator, std::vector<int>::iterator> maxs = 
        std::equal_range(vec.begin(), vec.end(), element);
    std::cout << std::distance(maxs.first, maxs.second) << std::endl;
    return 0;
}

Если у вас используется сортировка, то надобность в алгоритме std::max_element просто отпадает. Достаточно отсортировать в убывающем порядке, а затем вывести в поток все элементы, которые совпадают с первым элементом контейнера.

Так что у вас есть еще пути совершенствования вашего алгоритма!

Например, так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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> maxs = 
        std::equal_range(vec.begin(), vec.end(), *v.begin() );
    std::cout << std::distance(maxs.first, maxs.second) << std::endl;
    return 0;
}

@CyBOSSeR · 30.08.2011, 20:43

Сообщение от Сыроежка

Что касается ваших ссылок на посты, то я имел в виду хронологию, что алгоритм уже написан в ранее обсуждаемой аналогичной теме.

Во-первых, на форуме с большой вероятностью это же задача уже решалась таким же способом. Во-вторых, с чего Вы взяли, что alex_x_x видел Ваше решение? На форуме, а тем более в этом разделе, темы плодятся пачками, Вы сами-то все посты читаете, а?
Насчет некоректности, вот код alex_x_x:

Сообщение от alex_x_x

C++
1
2
3
4
5
6
7
8
9
10
11
12
template<typename T> 
struct Comp
{
   Comp() : count(0) {}
   void operator() (const T& t) 
   {
      if (t > max || 0 == count){ max = t; count = 1; }
      else if (t==max) ++count;
   }   
int count;
   T max; 
};

Где здесь некоректность? Философские споры об именовании и выборе подходящих типов откинем как не имеющие отношения к корретности/некорректности решения.

@diagon · 30.08.2011, 20:44

Или так(может, уже было, лень всю тему листать)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <map>
#include <algorithm>
int main()
{
    int arr[] = { 1, 2, 3, 5, 4, 5, 3 };
    
    std::map<int, int> map;
    
    std::for_each( arr, arr + sizeof(arr) / sizeof(*arr), [&map] (int x)
    {
        ++map[x];
    } );
    
    std::cout << (*--map.end()).second;
}

@Сыроежка · 31.08.2011, 18:48

Сообщение от CyBOSSeR

Во-первых, на форуме с большой вероятностью это же задача уже решалась таким же способом. Во-вторых, с чего Вы взяли, что alex_x_x видел Ваше решение? На форуме, а тем более в этом разделе, темы плодятся пачками, Вы сами-то все посты читаете, а?
Насчет некоректности, вот код alex_x_x:

Где здесь некоректность? Философские споры об именовании и выборе подходящих типов откинем как не имеющие отношения к корретности/некорректности решения.

Я уже писал, где здесь некорректность. Не инициализирована переменная max. Поэтому алгоритм вообще не будет корректно работать. Кроме того грамотно писать не

C++
1
if (t > max || 0 == count)

а

C++
1
[CPP]if (0 == count || max < t)

[/CPP]

Заметили два различия? Именно два, а не одно? Первый исходный код просто является безграмотным, не говоря уж о том, что некорректным.

@easybudda · 31.08.2011, 19:12

Сообщение от Сыроежка

Кроме того грамотно писать...

Кстати да, прав Сыроежка. В принципе если эту строчку заменить, то и не важно, что max не инициализирована.

Сообщение от diagon

может, уже было

Ага, на предыдущей странице 62 пост 2 вариант...

@Сыроежка · 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 не инициализирована.

Здесь также следует обратить внимание, что используется оператора >, тогда как для элементов контейнера требуется определение оператора <, а не >. То есть со многими определенными пользователем типами алгоритм не будет работать, так как пользователи не видят необходимости определять оператор >.

@CyBOSSeR · 31.08.2011, 19:38

Сообщение от Сыроежка

C++
1
if (t > max || 0 == count)

Не инициализирована переменная max. Поэтому алгоритм вообще не будет корректно работать.

Алгоритм будет работать корректно. В max будет мусор в случае если T будет являтся примитивным типом, это, конечно, факт, но на работу это не повлияет. При первом же вызове оператора каким бы ни было значение max условие 0 == count будет истинным, а следственно произойдет присваивание max'у значения первого элемента последовательности. Проверьте.

Сообщение от Сыроежка

Первый исходный код просто является безграмотным, не говоря уж о том, что некорректным.

Это не production код, это код собранный на коленке для форума, в котором, естественно, могут быть огрехи. И это нужно понимать прежде чем бросатся с обвинениями в "непрофессионализме".

@Сыроежка · 31.08.2011, 19:43

Сообщение от CyBOSSeR

Алгоритм будет работать корректно. В max будет мусор в случае если T будет являтся примитивным типом, это, конечно, факт, но на работу это не повлияет. При первом же вызове оператора каким бы ни было значение max условие 0 == count будет истинным, а следственно произойдет присваивание max значения первого элемента последовательности. Проверьте.

Вы заблуждаетесь! max может быть не "примитивным" типом, как вы пишите, а определенным пользователем объектом, который необязательно должен быть инициализирован конструктором по умолчанию. Кроме того, это значение max может случайно совпасть со значением элемента, и тогда вы счетчик увеличите на единицу.

Так что проблема не во мне, а в том, что вы этого не видите!

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

Сообщение от CyBOSSeR

Это не production код, это код собранный на коленке для форума, в котором, естественно, могут быть огрехи. И это нужно понимать прежде чем бросатся с обвинениями в "непрофессионализме".

Код, собранный на коленках, может содержать опечатки, или какие-нибудь пропуски. Но тем не менее он должен быть написан грамотно.

Вы просто, как и многие не высококвалифицированные программисты, не понимаете простой вещи, что профессионал всегда пишет грамотный код. То есть нет у него такого, что в одном случае он пишет безграмотный код, а в другом случае грамотный. Он просто не способен писать безграмотный код, так как этому мешает его профессиональный опыт. Я вам уже написал выше, что означает профессионально написанный код. Вы же там ждали какого-то чуда, и это чудо считали профессионально написанным кодом.

Я смотрю, вы многое в программировании не понимаете!

@CyBOSSeR · 31.08.2011, 19:49

Сообщение от Сыроежка

max может быть не "примитивным" типом, как вы пишите, а определенным пользователем объектом, который необязательно должен быть инициализирован конструктором по умолчанию.

Как этот факт отражен в Вашем решении? И как Вы предлагаете обойти эту ситуацию?

Сообщение от Сыроежка

Кроме того, это значение max может случайно совпасть со значением элемента, и тогда вы счетчик увеличите на единицу.

О чем вы? Каким бы нибыло значение max при первом вызове будет выполнено тело первого условного оператора. Посмотрите внимательно.

Сообщение от Сыроежка

Так что проблема не во мне, а в том, что вы этого не видите!

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

Сообщение от Сыроежка

Вы просто, как и многие не высококвалифицированные программисты, не понимаете простой вещи, что профессионал всегда пишет грамотный код. То есть нет у него такого, что в одном случае он пишет безграмотный код, а в другом случае грамотный. Он просто не способен писать безграмотный код, так как этому мешает его профессиональный опыт. Я вам уже написал выше, что означает профессионально написанный код. Вы же там ждали какого-то чуда, и это чудо считали профессионально написанным кодом.

Мда... Печаль... Вы либо слишком молоды, либо слишком категоричны.

@easybudda · 31.08.2011, 20:11

Сообщение от CyBOSSeR

Алгоритм будет работать корректно.

Странно, но работает. Я-то думал, что если t <= max, то чему там count равно уже не проверяется... Или ещё какой-то тонкости не улавливаю?

Вот кстати ещё одно очень простое любительское решение

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <algorithm>
 
int main(){
    const int size(10);
    int arr[size] = { 1, 3, 5, 3, 2, 5, 4, 3, 1, 2 };
    int me = *std::max_element(arr, arr + size);
    std::cout << "Max element: " << me << " meets " << std::count(arr, arr + size, me) << " times" << std::endl;
    
    return 0;
}

Может тоже было, но на вскидку не нашёл в этой теме.

Сообщение от Сыроежка

Вы просто, как и многие не высококвалифицированные программисты, не понимаете...

Вот ей-богу надоело уже! Оставьте при себе своё мнение о профессионализме участников форума, а то ведь в правилах есть пункт "неуважительное отношение". С совсем небольшой натяжкой вполне применим. Надо оно Вам?

Добавлено через 4 минуты
А чем, кстати, по умолчанию поля типа int в классе инициализируются? Случайно не INT_MIN (ну или как там в С++ правильно минимальное значение обозначается)? А то есть подозрение, что минимальный элемент вот как-раз из-за этого нюанса и не найдётся, и не посчитается...

Новые блоги и статьи Все статьи Все блоги /
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .

@валентин777 0 / 0 / 0 Регистрация: 01.06.2011 Сообщений: 45

	Определить количество максимальных элементов в массиве. 26.08.2011, 19:26. Показов 26114. Ответов 88 Метки нет (Все метки) Дан одномерный массив. Определить количество максимальных элементов в массиве. 0

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

Решение