Несколько мод числового ряда c++

283
26 ноября 2016, 18:59

Делаю задания по книге Бьярне Страуструпа "Программирование: принципы и практика с использованием C++, 2-е издание". Во главе 4, задании 16 надо найти моду числового ряда. С одной модой проблем не возникло, а что делать когда в числовом ряде несколько мод? Например, если в ряде 4, 8, 8, 4, 9; мода же и 4, и 8.

vector<double> numbers;
for (double n; cin >> n;)
    numbers.push_back(n);
sort(numbers);
int counter = 0; 
for (int i = 0; i < numbers.size(); ++i) 
{
    for (int j = 0; j < numbers.size(); ++j) 
    {
        if (numbers[i] == numbers[j])
            ++counter;
    }
    //сколько каждое число повторяется раз
    arr.push_back(counter);
    counter = 0;
}

int n = 0;
double max = 0;
for (int i = 0; i < arr.size(); ++i) 
{
    if (arr[i] == 1) 
        ++counter;
    if (arr[i] > max) 
    {
        max = arr[i];
            n = i;
    }
}
if (counter == arr.size())
    cout << "We dont have mode\n";
else
    cout << "Mode: " << numbers[n] << '\n';

keep_window_open("~");
return 0;
Answer 1

У вас эти циклы

int counter = 0; 
for (int i = 0; i < numbers.size(); ++i) 
{
    for (int j = 0; j < numbers.size(); ++j) 
    {
        if (numbers[i] == numbers[j])
            ++counter;
    }
    //сколько каждое число повторяется раз
    arr.push_back(counter);
    counter = 0;
}

не эффективны. Так как вектор был уже отсортирован, то не имеет смысла начинать внутренний цикл с позиции, равной 0.

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

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

#include <iostream>
#include <vector>
#include <algorithm>
int main() 
{
    std::vector<int> v = { 4, 8, 8, 4, 9 };
    std::vector<int> mods;
    std::sort( v.begin(), v.end() );
    using size_type = std::vector<int>::size_type;
    size_type max = 0;
    for ( size_type i = 0, j; i < v.size(); i = j )
    {
        j = i + 1;
        while ( v[j] == v[i] ) ++j;
        if ( max <= j - i )
        {
            if ( max != 1 )
            {
                if ( max < j - i )
                {
                    max = j - i;
                    mods.assign( 1, v[i] );
                }
                else
                {
                    mods.push_back( v[i] );
                }
            }
        }           
    }
    if ( max == 1 )
    {
        std::cout << "We dont have mode\n";
    }       
    else
    {
        std::cout << "Mode" << ( mods.size() == 1 ? ":" : "s:" );
        for ( int x : mods ) std::cout << ' ' << x;
        std::cout << '\n';
    }       
    return 0;
}

Ее вывод на консоль следующий

Modes: 4 8
Answer 2

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

Я бы ввел две переменные - значение моды и количество ее повторов (изначально - 0).

Далее, идя от первого значения вектора, просто подсчитывал бы, сколько раз встречается очередное значение вектора (в вашем случае - 4 4 8 8 9, значит, первое - 4, второе - 4, третье - нет; останавливаемся. Текущий счетчик 0. Он меньше полученного? да. Записываем новый счетчик - 2, новую моду - 4. Продолжаем с третьего элемента. 8, четвертый 8, пятый... стоп. Счетчик - 2. Записанный счетчик меньше? Нет? игнорируем. (Или, если проверять с помощью >= - то да, перезаписываем счетчик 2, моду - 8). Продолжаем с пятого элемента. 9, вектор кончился. Повторение - одно, меньше счетчика, игнорируем.

Так вы пройдете по вектору только один раз. Иначе зачем вы его сортировали? :)

Answer 3

Вот еще вариант, не скажу что оптимальный, но простой и наглядный:

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
  // -- вектор значений 
  std::vector<int> Array = {7,5,3,2,2,4,5,7,9,0,1,1,4}; 
  // -- карта частот 
  std::unordered_map<int,int> Freq;
  for(auto &i:Array) Freq[i]++;
  // -- сортировка по частотам
  std::vector<std::pair<int, int>> Vec(Freq.begin(),Freq.end());
  std::sort(Vec.begin(),Vec.end(),[](std::pair<int,int> a, std::pair<int,int> b) {
    return (a.second == b.second) ? a.first > b.first : a.second > b.second;
  });
  // -- вывод пар по убыванию частот и по убыванию значений
  for(auto &i:Vec) std::cout << i.first << ":" << i.second << std::endl;
  // -- если нужен один элемент - возмем первый
} 

Вывод будет такой:

7:2
5:2
4:2
2:2
1:2
9:1
3:1
0:1
Answer 4

У меня получился ещё такой вариант.

vector<int> repeats;
vector<int> numbers = { 4, 8, 8, 4, 9 };
sort(numbers);
int counter = 0;
for (int i = 0; i < numbers.size(); ++i)
{
    for (int j = 0; j < numbers.size(); ++j)
    {
        if (numbers[i] == numbers[j])
            ++counter;
    }
    //сколько каждое число повторяется раз
    repeats.push_back(counter);
    counter = 0;
}
vector<int> num;
vector<int> rep;
for (int i = 0; i < repeats.size(); ++i)
{
    //если счетчик равен кол-ву 
    //значений в векторе - значит все числа
    //повторяются 1 раз и моды нет
    if (repeats[i] == 1)
        ++counter;
    //Удаление повторяющихся чисел и их повторов
    if (i == 0 || numbers[i - 1] != numbers[i])
    {
        num.push_back(numbers[i]);
        rep.push_back(repeats[i]);
    }
}
int n = 0;
int max = 0;
for (int i = 0; i < num.size(); ++i)
{
    if (rep[i] > max)
    {
        max = rep[i];
        n = i; //индекс макимального кол-ва повторения
    }
}

cout << "\n";
if (counter == repeats.size())
    cout << "We dont have mode\n";
else
    for (int i = 0; i < num.size(); ++i)
        //если максимальное повторение такое же выводим ещё моды
        if (rep[i] == rep[n]) 
            cout << "Mode: " << num[i] << '\n';

Вывод на консоль:

Mode: 4 
Mode: 8
READ ALSO
MinGW или Cygwin?

MinGW или Cygwin?

Раньше просто компилировал с помощью g++ на Ubuntu, вытягивая компилятор с помощью пакетного менеджера:

358
стандарты GNU C++ и GNU C++11

стандарты GNU C++ и GNU C++11

Почему gcc компилирует этот код для стандарта GNU C++, но не компилирует для GNU C++11?

261
return &hellip; или return (&hellip;)

return … или return (…)

Часто вижу, что выражение, которое возвращает return, заключено в круглые скобкиНапример, в хедере set в Visual Studio 2015 во всех функциях, возвращающих...

231
Эхо сервер на двух разных машинах, подключенных к одному wifi с\с++

Эхо сервер на двух разных машинах, подключенных к одному wifi с\с++

Есть две машины на Linux, подключённые к одному Wi-Fi роутеруНужно реализовать на них эхо-сервер на C\C++

228