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

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

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

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

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

  1. Nik:

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

  2. Vladimir:

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

  3. fo:

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

    • В массиве счёта 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]++

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

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

https://www.litres.ru/d-m-zlatopolskiy/sbornik-zadach-po-programmirovaniu-2889665/?lfrom=15589587

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

Яндекс.Метрика