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

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

Войти
Регистрация
Восстановить пароль
 
Vetaliuy
0 / 0 / 0
Регистрация: 24.04.2011
Сообщений: 18
#1

Найти моду в массиве - C++

10.07.2012, 12:08. Просмотров 4099. Ответов 13
Метки нет (Все метки)

Найти в массиве моду. *Массив размером m, m – натурал. число.
(мода- элемент ряда, который встречается наиболее часто.)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2012, 12:08     Найти моду в массиве
Посмотрите здесь:

Ребята, как найти моду ряда чисел?=) C++
C++ Не могу найти ошибку с подсчетом суммы элементов в интервале[a,b] в динамическом одномерном массиве массиве.
C++ В массиве X(N) найти значение максимального элемента массива и найти, сколько таких элементов.
Найти в массиве минимальный и максимальный элементы. Вывести последовательность значений из этого диапазона, не встречающихся в данном массиве C++
C++ Найти в массиве максимальный и минимальный элементы в массиве и их количество
где моду прочитать о деревьях с нуля? C++
C++ Найти среднее, моду и медиану по заданному массиву
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
10.07.2012, 12:29     Найти моду в массиве #2
Код написан здесь
Мода массива
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 241
10.07.2012, 12:31     Найти моду в массиве #3
Каковы максимальные значения m,n ???
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
10.07.2012, 12:38     Найти моду в массиве #4
Цитата Сообщение от LVV Посмотреть сообщение
Каковы максимальные значения m,n ???
А откуда еще n взялось?
Массив одномерный размера m.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 241
10.07.2012, 21:25     Найти моду в массиве #5
В задаче не указан максимальный размер массива (m) и не указано, какие значения могут принимать элементы массива . Предположим, что речь идёт массиве натуральных чисел, максимальное из которых n<32768.

запустите программу и посмотрите сколько времени занимает поиск моды в моём варианте, и в предложенной ссылке Мода массива для массива из 30000 элементов (я объединил оба кода)
А, скажем, для 100000 элементов... не дождётесь второго результата (а мой - почти мгновенно).
Вот поэтому я и спрашивал, каков размер массива () и каково максимальное значение его элементов.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//moda
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
    srand(time(NULL));
    setlocale (0,"");
    //СОЗДАНИЕ МАССИВА
    int m=30000, // размер массива
        n=10, // максимальное значение элемента массива (n<32768)
        rmax; // мода
    int *a = new int[m];
    for (int i=0; i<m; i++)
    a[i]= rand() % (n+1);
    
    //ВЫВОД МАССИВА
        //for (int i=0; i<m; i++)
        //cout << a[i]<< " ";
        //cout << endl;
    
    cout << "массив из " << m << " элементов создан,\n\n\n\n";
    
    
 
    //мой вариант
    cout << "идёт проверка предложенным мною способом\n\n";
    int b[32768] ={0};
    for (int i=0; i<m; i++)
        b[a[i]]++;
    
    rmax=b[0];
    int I=0;
    for (int i=0; i<n; i++)
        if (b[i]>rmax)
        {
            rmax=b[i];
            I=i;
        }
    cout << "элемент " << I 
        << "\nвстречается наибольшее количество: " 
        << rmax << " раз\n\n\n\n" <<endl;
    
 
    //предложенный вариант 
        cout <<"идёт проверка предложенным Inadequate способом\n" ;
    rmax = 0;
    int max = a[0], cmax = 0;
        
    for (int i = 0; i < m; i++) 
    {
        if (cmax > rmax) 
        {
            rmax = cmax;            
            max = a[i - 1];    
        }
        cmax = 0;
        for (int j = i; j < m; j++)
           if (a[j] == a[i])
              cmax++;
    }
    cout << "элемент " << max 
        << "\nвстречается наибольшее количество: " 
        << rmax << " раз\n\n\n\n" <<endl;
    
    
system ("pause");
}
P.S. Оба кода моду ищут правильно, только мой - для наименьшего числа массива, а предложенный по ссылке - первого из нескольких.
Roof
 Аватар для Roof
154 / 154 / 10
Регистрация: 03.11.2010
Сообщений: 393
11.07.2012, 15:44     Найти моду в массиве #6
В своем коде вы избавились от вложенного цикла за счет второго массива и получили лучшую скорость, это хорошо. За это плюсую.
Vinchi
0 / 0 / 0
Регистрация: 11.07.2012
Сообщений: 3
27.08.2012, 19:09     Найти моду в массиве #7
Цитата Сообщение от LVV Посмотреть сообщение
В задаче не указан максимальный размер массива (m) и не указано, какие значения могут принимать элементы массива . Предположим, что речь идёт массиве натуральных чисел, максимальное из которых n<32768.

запустите программу и посмотрите сколько времени занимает поиск моды в моём варианте, и в предложенной ссылке Мода массива для массива из 30000 элементов (я объединил оба кода)
А, скажем, для 100000 элементов... не дождётесь второго результата (а мой - почти мгновенно).
Вот поэтому я и спрашивал, каков размер массива () и каково максимальное значение его элементов.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//moda
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
    srand(time(NULL));
    setlocale (0,"");
    //СОЗДАНИЕ МАССИВА
    int m=30000, // размер массива
        n=10, // максимальное значение элемента массива (n<32768)
        rmax; // мода
    int *a = new int[m];
    for (int i=0; i<m; i++)
    a[i]= rand() % (n+1);
    
    //ВЫВОД МАССИВА
        //for (int i=0; i<m; i++)
        //cout << a[i]<< " ";
        //cout << endl;
    
    cout << "массив из " << m << " элементов создан,\n\n\n\n";
    
    
 
    //мой вариант
    cout << "идёт проверка предложенным мною способом\n\n";
    int b[32768] ={0};
    for (int i=0; i<m; i++)
        b[a[i]]++;
    
    rmax=b[0];
    int I=0;
    for (int i=0; i<n; i++)
        if (b[i]>rmax)
        {
            rmax=b[i];
            I=i;
        }
    cout << "элемент " << I 
        << "\nвстречается наибольшее количество: " 
        << rmax << " раз\n\n\n\n" <<endl;
    
 
    //предложенный вариант 
        cout <<"идёт проверка предложенным Inadequate способом\n" ;
    rmax = 0;
    int max = a[0], cmax = 0;
        
    for (int i = 0; i < m; i++) 
    {
        if (cmax > rmax) 
        {
            rmax = cmax;            
            max = a[i - 1];    
        }
        cmax = 0;
        for (int j = i; j < m; j++)
           if (a[j] == a[i])
              cmax++;
    }
    cout << "элемент " << max 
        << "\nвстречается наибольшее количество: " 
        << rmax << " раз\n\n\n\n" <<endl;
    
    
system ("pause");
}
P.S. Оба кода моду ищут правильно, только мой - для наименьшего числа массива, а предложенный по ссылке - первого из нескольких.
Спасибо!
Использовал ваш код,но немного переделал под vector.
И ещё раз большое спасибо!
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
int main()
{
    vector<int> moda;
    vector<int> number(1000,0);
    
    int num;
    int rmax;
    int n = 100;
    
    while(cin >> num)
        moda.push_back(num);
    
    for (int i = 0;i < moda.size();i++)
        number[moda[i]]++;
    
    rmax = number[0];
    int c = 0;
    
    for (int i = 0; i < n;i++)
        if(number[i] > rmax)
        {
            rmax = number[i];
            c = i;
        }
    
    cout << "Repeat numbers: " << c << endl
         << "The number of repetitions: " << rmax << endl;
    
}
agvk
0 / 0 / 0
Регистрация: 17.11.2014
Сообщений: 3
08.11.2015, 19:26     Найти моду в массиве #8
в универе написал, вроде как работает. код на Си
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
 
#pragma warning(disable: 4996)
 
#define N 20
system();
 
int main(void){
    int A[N];
    int i = 0,
        j = 0,
        len = 0,
        curNum = 0, //chastota vstrechanii
        maxNum = 0, //chastota modi
        curModa = 0, //tekuschaya moda
        maxModa = 0,
        flag = 0;
 
        printf("Insert array A[], a number of elements max 20: ");
        scanf("%d", &len);
 
    while(1){
        if(!scanf("%d", &A[i])){
            printf("Wrong enter!\n");
            printf("Insert array A[], a number of elements = %d\n", len);
            fflush(stdin);
            i = 0;
        }
        i++;
        if(i == len){
            break;
        }
    }
 
    for (i = 0; i < len; i++){
        curNum = 0;
        for(j = 0; j < len; j++){
            if(A[i]==A[j]){
                curNum++;
            }
        }
        if(curNum > maxModa){
            flag = 1;
            maxModa = curNum;
            maxNum = A[i];
        }
        else if(curNum == maxModa && A[i] != maxNum){
            flag = 0;
        }
        
        curModa = maxNum;
    }
 
    if(flag){
        printf("chastota vstrechanii: %d\nmoda: %d\n", maxModa, curModa);
    }
    else{
        printf("No moda\n");
        system("PAUSE");
        return;
    }
 
    system("PAUSE");
    return 0;
}
pproger
163 / 66 / 13
Регистрация: 22.03.2011
Сообщений: 188
08.11.2015, 21:52     Найти моду в массиве #9
Vetaliuy,

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
40
41
42
43
44
45
#include <iostream>
#include <map>
#include <vector>
 
template <typename T>
T find_mode(const std::vector<T> &v) {
    using MyMap = std::map<T, int>;
 
    MyMap m;
 
    for (const auto &i : v) {
        ++m[i];
    }
 
    typename MyMap::iterator i = std::max_element(m.begin(), m.end(),
            [](const typename MyMap::value_type &lh, const typename MyMap::value_type &rh) { return lh.second < rh.second; }
    );
 
    return i->first;
}
 
int main() {
    using std::cout;
    using std::endl;
 
    std::vector<std::string> str_arr = {
        "111",
        "111",
        "222",
        "absafasfa",
        "222",
        "111",
        "absafasfa",
        "absafasfa",
        "absafasfa",
        "333",
        "222",
        "absafasfa",
    };
 
    std::vector<int> int_arr = { 1, 2, 5, 1, 3, 2, 2, 2, 2, 1 };
 
    cout << find_mode(str_arr) << endl;
    cout << find_mode(int_arr) << endl;
}
Pashtets
0 / 0 / 0
Регистрация: 30.12.2016
Сообщений: 14
25.01.2017, 00:41     Найти моду в массиве #10
Цитата Сообщение от LVV Посмотреть сообщение
/
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/предложенный вариант 
 cout <<"идёт проверка предложенным Inadequate способом\n" ;
 rmax = 0;
 int max = a[0], cmax = 0;
for (int i = 0; i < m; i++) 
 {
 if (cmax > rmax) 
 {
 rmax = cmax; 
 max = a[i - 1]; 
 }
 cmax = 0;
 for (int j = i; j < m; j++)
 if (a[j] == a[i])
 cmax++;
 }
 cout << "элемент " << max 
 << "\nвстречается наибольшее количество: " 
 << rmax << " раз\n\n\n\n" <<endl;
system ("pause");
}
как этот код вообще может чтото искать если в самом начале rmax = 0;
и cmax = 0;
а дальше ниже в цикле проверяется выражение if (cmax > rmax)
как они могут быть больше или меньше если они оба по условию равны нулю и нигде до этого момента в них не внисится изменение

Добавлено через 26 минут
Цитата Сообщение от Vinchi Посмотреть сообщение
C++
1
2
for (int i = 0;i < moda.size();i++)
 number[moda[i]]++;
объясните плс как работает код целиком... и зачем нам нужен такой цикл с итерацией. Что делает итерация я чет не въеду.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 241
25.01.2017, 14:10     Найти моду в массиве #11
Мода - это значение, которое встречается наибольшее количество раз.
Один из способов поиска моды заключается в многократном просмотре исходного массива a[] и подсчете количества повторений его одинаковых элементов.

Второй способ, заключается в использовании дополнительного целочисленного массива b[], и однократном прохождении исходного массива a[]. Этот способ удобен для целочисленного массива a[] с неотрицательными значениями элементов, поскольку эти значения будут использоваться в качестве индексов массива b[]


Например, дан целочисленный массив a[1000], значения элементов которого не отрицательны и не превышают 10. Определим и обнулим новый массив b[11], максимальный индекс которого (10) равен максимально возможному значению элемента массива a[1000]
int b[11] ={};
Просмотрим массив a[1000], увеличивая на единицу элементы массива b c индексами, равными значениям элементов массива а
for (int i=0; i<1000; i++)
b[a[i]]++;

Таким образом значения элементов массива b[11] станут счетчиками, обозначающими сколько раз встречается в массиве a[1000] любое значение от 0 до 10-ти включительно.
Например значение b[5] покажет сколько раз в массиве a[1000] повторилось число 5.
Для нахождения моды массива a[1000] достаточно будет найти индекс наибольшего элемента массива b[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
#include <iostream>
#include <map>
using namespace std;
int main()
{
//дан массив вещественных чисел
    double a[5]={1.8, 1.4, 2.9, 1.5, 2.9} ;
//находим моду
map <double,int> b;
     for(int i=0; i<5; i++)
     b[a[i]]++;
map <double, int>::iterator it = b.begin();
   double mod = (*it).first;
   int max = (*it).second;;
         for (; it!=b.end(); it++)
          if ((*it).second > max)
            {
               max = (*it).second;
               mod = (*it).first;
           }
cout << mod << endl;
return 0;
}


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
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
//дан массив строковых элементов
    string a[5]={"abc", "abcd", "kl", "fgh", "kl"} ;
//находим моду
    map <string,int> b;
for(int i=0; i<5; i++)
b[a[i]]++;
map <string, int>::iterator it = b.begin(); 
string mod = (*it).first;
int max = (*it).second;;
    for (; it!=b.end(); it++)
        if ((*it).second > max)
        {
            max = (*it).second;
            mod = (*it).first;
        }
cout << mod << endl;
return 0;
}
Peoples
979 / 495 / 377
Регистрация: 06.02.2016
Сообщений: 1,306
Записей в блоге: 10
Завершенные тесты: 3
25.01.2017, 15:21     Найти моду в массиве #12
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int>v {1,2,2,3,4,4,5,5,5,5,5,6,7,8,8,8,8};
    cout<<*max_element(v.cbegin(),v.cend(),[&v](const int &x, const int &y) {
        return count(v.cbegin(),v.cend(),x)<count(v.cbegin(),v.cend(),y);
    });
}
Pashtets
0 / 0 / 0
Регистрация: 30.12.2016
Сообщений: 14
25.01.2017, 23:50     Найти моду в массиве #13
LVV, я новичок, поэтому и решил эту задачу по своему...
Ниже код моего варианта поиска моды:
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
int main() {
    setlocale(LC_ALL, "ru");
 
    vector <int> nums = {7,2,3,12,1,1,1,1,1,1,6,7,7,8,7};
    vector <int> moda;
 
    sort(nums);
    for (int i = 1; i < nums.size()-1; i++) {
        if (nums[i] == nums[i - 1]) {
            moda.push_back(nums[i]);
            if (nums[i] != nums[i + 1]) {
                moda.push_back(nums[i]);
            }
        }
    } 
    sort(moda);
    int b = moda[0],
        a = 0,
        c = 0;
    for (int i = 0; i < moda.size(); i++) {
        if (moda[i] == b) {
            a = moda[i];
            c++;
        }   
    }
    cout << "Повторяемое число " << a << " повторяется " << c << " раз(а)" << endl;
 
        /*for (int i : nums2) {
        cout << i << endl;
    }*/
        return 0;
 
}
В этом случае, такой алгоритм находит только 1 моду, ну я имею ввиду если в массиве будет 2 числа с одинаковым кол-вом повторений, то найдется только вариант число которого меньше. Но немного поковырять можно будет настроить, чтобы показывалось равенство двух или нескольких равных по количеству повторений цифр.
в этом случае нам не нужен массив размером в 1000 итд.

Сравнить время работы программ точно не смог, пробовал выполнить функцией clock(); но погрешность была очень большая.

Чет вчитываюсь в ваш вариант не все понимаю...
P.S. хотелось бы услышать критику, по поводу этого варианта.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2017, 06:25     Найти моду в массиве
Еще ссылки по теме:

C++ В двухмерном массиве найти максимальный и минимальный элементы и их координаты в массиве
C++ В массиве найти числа после первого отрицательного и найти их сумму
Массивы: найти моду, стоит ли изобретать колесо!? C++
C++ Найти наибольший элемент в массиве A которого нет в массиве B
C++ Найти моду последовательности за линейное время O(N)

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

Или воспользуйтесь поиском по форуму:
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 241
26.01.2017, 06:25     Найти моду в массиве #14
Цитата Сообщение от Pashtets Посмотреть сообщение
Чет вчитываюсь в ваш вариант не все понимаю...
Для целых неотрицательных чисел всё очень просто (читай описание выше):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[5]={10,2,0,10,5},
 b[11]={};
for(int i=0; i<5; i++}
b[a[i]]++;
 
int max=b[0],
 moda=0;
 
for(int i=0; i<11; i++)
    if(b[i]>max)
    {
        max=b[i];
        moda=i;
      }
 
cout << moda;
Для вещественного массива ниже код с комментариями:
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
#include <iostream>
#include <map>
using namespace std;
int main()
{
//дан массив вещественных чисел
    double a[5]={1.8, 1.4, 2.9, 1.5, 2.9} ;
//обьявляем контейнер b
//первое значение (first) - ключ
//второе значение (second) - счетчик
    map <double,int> b;
// просматриваем массив а
for(int i=0; i<5; i++)
// увеличиваем счетчик контейнера b
//для соответствующих ключей 
b[a[i]]++;
 
//ищем максимальный счетчик max
//и моду moda в контейнере b
map <double, int>::iterator it = b.begin();//обьявляем итератор 
//пусть искомые значения находятся в начальном элементе контейнера b 
double moda = (*it).first;
int max = (*it).second;;
 
 
for (; it!=b.end(); it++)//пока не достигли последнего указателя
{
    if ((*it).second > max)//если нашелся счетчик больше, чем сохранённый максимальный
    {
        max = (*it).second;
        moda = (*it).first;
    }
}
//выводим моду (ключ с наибольшим счетчиком)
cout << moda << endl;
 
return 0;
}
Цитата Сообщение от Peoples Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int>v {1,2,2,3,4,4,5,5,5,5,5,6,7,8,8,8,8};
cout<<*max_element(v.cbegin(),v.cend(),[&v](const int &x, const int &y) {
return count(v.cbegin(),v.cend(),x)<count(v.cbegin(),v.cend(),y);
});
}
А на Visual Studio код от Peoples пошел лишь после переделки строки инициализации вектора
Yandex
Объявления
26.01.2017, 06:25     Найти моду в массиве
Ответ Создать тему
Опции темы

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