Делаю задания по книге Бьярне Страуструпа "Программирование: принципы и практика с использованием 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;
У вас эти циклы
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
Выводите любую :) - она и будет модой. Но позвольте дать совет, как поступить. Вы сейчас перебираете для каждого встреченного в векторе числа все остальные числа. Зачем, если вектор уже отсортирован?
Я бы ввел две переменные - значение моды и количество ее повторов (изначально - 0).
Далее, идя от первого значения вектора, просто подсчитывал бы, сколько раз встречается очередное значение вектора (в вашем случае - 4 4 8 8 9, значит, первое - 4, второе - 4, третье - нет; останавливаемся. Текущий счетчик 0. Он меньше полученного? да. Записываем новый счетчик - 2, новую моду - 4. Продолжаем с третьего элемента. 8, четвертый 8, пятый... стоп. Счетчик - 2. Записанный счетчик меньше? Нет? игнорируем. (Или, если проверять с помощью >= - то да, перезаписываем счетчик 2, моду - 8). Продолжаем с пятого элемента. 9, вектор кончился. Повторение - одно, меньше счетчика, игнорируем.
Так вы пройдете по вектору только один раз. Иначе зачем вы его сортировали? :)
Вот еще вариант, не скажу что оптимальный, но простой и наглядный:
#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
У меня получился ещё такой вариант.
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
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Раньше просто компилировал с помощью g++ на Ubuntu, вытягивая компилятор с помощью пакетного менеджера:
Почему gcc компилирует этот код для стандарта GNU C++, но не компилирует для GNU C++11?
Часто вижу, что выражение, которое возвращает return, заключено в круглые скобкиНапример, в хедере set в Visual Studio 2015 во всех функциях, возвращающих...
Есть две машины на Linux, подключённые к одному Wi-Fi роутеруНужно реализовать на них эхо-сервер на C\C++