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

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

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

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

2 комментария: С++ для начинающих Мода массива

  • Nik говорит:

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

  • Vladimir говорит:

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

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

Ваш e-mail не будет опубликован.

Поиск

 
     

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

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Отец перед сном рассказывает сыну сказку: - Жил на свете богатый человек. Купил он себе самый лучший компьютер и кучу лицензионных программ. - Пап, а как это - лицензионных? - Спи, сынок, я же сказал - это сказка! . .

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок