С++ для начинающих Мода массива

Опубликовано 26.07.2011 | Автор: admin

Одно из популярных заданий при работе с массивами — поиск моды.

Модой называют наиболее часто встречающееся или повторяющееся значение в массиве или интервале данных. Например, символ в строке, встречаемый наибольшее число раз, — мода.

Вникать мне пришлось в тему "моды" по книге Дейтелов, но вникнуть сразу не удалось.

Для решения любой задачи нужно прикинуть то, что может потребоваться. Т. е. нужен минимальный набор первоначальных данных. В моём случае будут использоваться цифры от 1 до 9: из этих цифр можно создать много различных последовательностей. В любой последовательности цифры могут повторяться, нам и предстоит выискивать то число, которое в последовательности встречается наибольшее число раз. Это и есть мода, которую нужно находить в задаче.

//clang       Мода массива        Код совсем новичкам         Листинг #1
#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;

int main(){
    srand(time(0u));        //для случайности

    const int N = 15;

    int arr[N] = {}; //основной массив
    int arr_of_count[10] = {}; //массив счёта

    //Случайное заполнение массива,
    //чтобы не заполнять клавиатурой

    for (unsigned i=0; i<N; i++){
            arr[i] = rand()%10; //Заполнение 0..9
            cout << arr[i] << ' ';
    }

    cout << '\n';

    //Заполняем массив счёта
    for (unsigned i=0; i<N; i++){
        arr_of_count[arr[i]]++;
    }
/*
    //Вывод массива счёта на экран
    for (unsigned i=0; i<10; i++){
        cout << arr_of_count[i] << ' ';
    }
*/

    cout << '\n';

    //Ищем максимум в массиве счёта
    int max_el = arr_of_count[0]; //устанавливаем начальное значение поиска
                                  //по первому элементу массива

    for (unsigned i=1; i<10;i++){
        if (max_el < arr_of_count[i]) max_el = arr_of_count[i];
    }

 //   cout << max_el << '\n';       //Вывести наибольшее число встреч

    cout << '\n';

    cout << "Mod list: ";
    //Выводим список на экран:
    unsigned count_summary = 0; //счётчик моды
    for (unsigned i=0;i<10;i++){
        if (arr_of_count[i] == max_el){
            cout << i << ' ';
            count_summary++; //наращиваем счётчик
        }
    }
    cout << "\n\n";

    cout << "summary: " << count_summary << '\n';   //вообще сколько таких элементов
    cout << "how many: " << max_el << '\n';         //сколько раз встречается в массиве
}

//clang Мода массива Код совсем новичкам Листинг #1

#include <iostream>

#include <time.h>

#include <stdlib.h>

using namespace std;

int main(){

srand(time(0u)); //для случайности

const int N = 15;

int arr[N] = {}; //основной массив

int arr_of_count[10] = {}; //массив счёта

//Случайное заполнение массива,

//чтобы не заполнять клавиатурой

for (unsigned i=0; i<N; i++){

arr[i] = rand()%10; //Заполнение 0..9

cout << arr[i] << ' ';

}

cout << '\n';

//Заполняем массив счёта

for (unsigned i=0; i<N; i++){

arr_of_count[arr[i]]++;

}

//Вывод массива счёта на экран

for (unsigned i=0; i<10; i++){

cout << arr_of_count[i] << ' ';

}

cout << '\n';

//Ищем максимум в массиве счёта

int max_el = arr_of_count[0]; //устанавливаем начальное значение поиска

//по первому элементу массива

for (unsigned i=1; i<10;i++){

if (max_el < arr_of_count[i]) max_el = arr_of_count[i];

}

// cout << max_el << '\n'; //Вывести наибольшее число встреч

cout << '\n';

cout << "Mod list: ";

//Выводим список на экран:

unsigned count_summary = 0; //счётчик моды

for (unsigned i=0;i<10;i++){

if (arr_of_count[i] == max_el){

cout << i << ' ';

count_summary++; //наращиваем счётчик

}

cout << "\n\n";

cout << "summary: " << count_summary << '\n'; //вообще сколько таких элементов

cout << "how many: " << max_el << '\n'; //сколько раз встречается в массиве

}

Поиск моды в массиве происходит в несколько вычислительных стадий, что вы можете увидеть в комментариях внутри листинга. Основную сложность мне в понимании, а следовательно и большому числу начинающих, доставило осознание того, что ячейку массива возможно использовать как индекс массива. Вспомогательный массив счёта (его можно назвать массивом рейтинга) — это подобие самого обычного счётчика, но только для массива значений. Основной фокус решения этой задачи в том, что в качестве значения используется непосредственно номер ячейки массива, а в значении ячейки оказывается счётчик встречаемости. При обходе основного массива каждый обходимый элемент считается номером ячейки вспомогательного, и значение по тому номеру во вспомогательном массиве увеличивается. Таким образом происходит счёт каждого элемента, если удобно, то "массивный счёт". Поскольку в условии, заданном мной, используется 10 чисел: [0;9], во вспомогательный массив задаётся 10 ячеек. Каждое встреченное число в основном массиве оказывается одной из цифр от 0 до 9. Если встреченное число 5, то во вспомогательном массиве происходит увеличение пятого элемента, если 8 — восьмого и т. п. Это вообще весь принцип поиска моды. Для поиска символа, например, можно задавать максимальное число элементов, равное числу символов в алфавите, либо 256 (в таблице ASCII 256 символов). Если нужно искать числа, то, соответственно, отталкиваться от общего числа уникальных чисел: нужен своеобразный алфавит и обязательно число его элементов. Это точка старта поиска моды. Дальше всё происходит по одному принципу.

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

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

Нижепоказываемый код новичкам понять будет очень сложно, поэтому если вы узнали основное, то не читайте дальше. Показываемый способ поиска моды для продвинутых новичков, знающих об STL библиотеке. Для того, чтобы следующий код работал, необходимо, чтобы компилятор поддерживал стандарт не ниже C++11. Для тех, кому слова "STL" и "C++11" не пустые, листинг #2 может добавить нужных знаний.

//clang     мода массива        Листинг #2
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <map>
#include <algorithm>

using namespace std;


int main(){
    random_device rd;   // non-deterministic generator
    mt19937 gen(rd());  // to seed mersenne twister.
    uniform_int_distribution<> dist(0,9); //
    vector<int> v;
    map<int,unsigned> m;

     for (int i = 0; i < 5; ++i) v.emplace_back(dist(gen));        //Массив и его заполнение случайными значениями

      cout << "our array is: ";
        for (const auto &i:v) cout << i << ' '; //Вывод значений массива на экран

     //Обход массива и запись в контейнер map
     for (unsigned i=0; i<v.size(); i++)  m[v[i]]++;    //массив счёта, подсчёт


        cout << '\n';
        for (const auto &i:m)  cout << i.first << ' ' << i.second << '|' << '\n'; //Вывод встреч: слева число, справа количество встреч


       //////////////////
       //Поиск максимального значения в map
            using pair_type = decltype(m)::value_type;  //автоматическое определение типов и синонимизация выведенного

            auto pr = max_element   //Использование алгоритма "max_element"
            (
                begin(m), end(m),
                [] (const pair_type & p1, const pair_type & p2) { //Лямбда-функция
                    return p1.second < p2.second;
                }
            );
            //std::cout << "A mode of the vector: " << pr->first << ' ' << pr->second << '\n'; //об этом позднее
       /////////////////


       //Результат поиска выводим на экран
        cout << "\nResult search:\n";
        for (const auto &i:m){
            if (i.second == pr->second) cout << i.second << ' ';
        }

        cout << '\n';
}

//clang мода массива Листинг #2

#include <iostream>

#include <vector>

#include <random>

#include <ctime>

#include <map>

#include <algorithm>

using namespace std;

int main(){

random_device rd; // non-deterministic generator

mt19937 gen(rd()); // to seed mersenne twister.

uniform_int_distribution<> dist(0,9); //

vector<int> v;

map<int,unsigned> m;

for (int i = 0; i < 5; ++i) v.emplace_back(dist(gen)); //Массив и его заполнение случайными значениями

cout << "our array is: ";

for (const auto &i:v) cout << i << ' '; //Вывод значений массива на экран

//Обход массива и запись в контейнер map

for (unsigned i=0; i<v.size(); i++) m[v[i]]++; //массив счёта, подсчёт

cout << '\n';

for (const auto &i:m) cout << i.first << ' ' << i.second << '|' << '\n'; //Вывод встреч: слева число, справа количество встреч

//////////////////

//Поиск максимального значения в map

using pair_type = decltype(m)::value_type; //автоматическое определение типов и синонимизация выведенного

auto pr = max_element //Использование алгоритма "max_element"

(

begin(m), end(m),

[] (const pair_type & p1, const pair_type & p2) { //Лямбда-функция

return p1.second < p2.second;

}

);

//std::cout << "A mode of the vector: " << pr->first << ' ' << pr->second << '\n'; //об этом позднее

/////////////////

//Результат поиска выводим на экран

cout << "\nResult search:\n";

for (const auto &i:m){

if (i.second == pr->second) cout << i.second << ' ';

}

cout << '\n';

}

Во многих случаях при решении этой задачи на поиск моды не учитывают некоторые возможные обстоятельства: может оказаться несколько максимальных значений, равных между собой. Чем больше массив, тем больше такая вероятность. Обычно находят какое-то одно значение и довольны, это, наверное, не очень правильно, поэтому я вывожу список. К тому же упоминал уже, что в некоторых случаях возможны ситуации, когда каждый элемент массива будет встречен только один раз. Если каждый элемент встречается только по разу, то я и не знаю, чем это считать: то ли моды нет, то ли всё мода. Чтобы определить такое положение дел, вам нужно проверить массива счёта на то, что каждый в нём элемент единичка. От этого и нужно будет отталкиваться.

В листинге #2 есть строка с комментарием, что "об этом позже". Если у вас есть определённая цель вытащить только один элемент из множества, или вы знаете, что в массиве исключительно одно значение встречается максимальное число раз, или что-то ещё, что однозначно требует вытаскивания одного значения, то некоторые действия можно пропустить: не нужно выискивать максимум, можно выводить сразу моду. В листинге #2 всё, что ниже той строки, будет уже не нужно. Только будьте внимательны, последнее (оговариваемое сейчас) хорошо, когда всё упирается в то, что значение нужно одно, иначе с дополнительными вычислениями всё, как в листингах #1 и #2.

Рубрика: map, STL, Базовые знания, level "HelloWorld", Массивы, Решения задач | Метки: map, одномерный массив

Nik:

03.08.2015 в 10:24 пп

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

Ответить

Vladimir:

09.05.2016 в 2:32 пп

Задание шикарное! Для новичков для понимания самое нужное, я потратил минут 40 чтоб разобраться что к чему. Честно сказать описание не особо помогает пониманию, но может это и к лучшему, я разобрался когда пропустил через дебаг по ступенькам.

fo:

27.01.2018 в 1:41 дп

Что означает это:

1	arr_of_count[arr[i]]++;

admin:

27.01.2018 в 2:10 дп

В массиве счёта arr_off_count выбирается индекс, который соответствует числу из массива arr[i], после чего увеличивается на 1 число в выбранной позиции массива счёта.
Например:
arr ==> 5,3,1,3
i == 0
arr[0] ==5 ==> arr_off_count[5]++
i == 1
arr[1] ==3 ==> arr_off_count[3]++
i == 2
arr[2] ==1 ==> arr_off_count[1]++
i == 3
arr[3] ==3 ==> arr_off_count[3]++

1

Ответить

Последние комментарии

Александр к записи Хороший стиль программирования
Аноним к записи Список тем сайта
Аноним к записи Список тем сайта

С++ для начинающих Мода массива

4 комментария на «“С++ для начинающих Мода массива”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета