Составьте программу поиска чаще всего встречающегося элемента массива С(М,М)

Question

Составьте программу поиска чаще всего встречающегося элемента массива С(М,М)

Comments

Для общего случая при достаточно больших М может потребоваться составление частотного словаря объемом М*М элементов. В случае значительного разброса значений элементов организовать какое-то хэширование данных в таком словаре в целях ускорения работы алгоритма будет затруднительно.

---

Возможный вариант реализации - формирование упорядоченной последовательности записей вида "ключ - количество повторений", где в качестве ключа выступают значения элементов массива С, а для поиска ключа в этой последовательности применяется бинарный поиск. Чтобы исключить постоянную сортировку при добавлении очередной записи, можно ввести вспомогательный индексный массив со ссылками на номера записей и выполнять сортировку в нем.

---

По сути, получаем примитивную реализацию того механизма, который используется в системах управления базами данных. Это делает задачу достаточно сложной. Другой вариант - использовать готовый компонент "Словарь", который имеется в PascalABC.NET версии 3.1

---

Есть сомнительный код, верно работающий только с положительными элементами. Словарь тут не вызвать, он ведь работает только для линейных последовательностей.Const n=3;Var ma:array[1..n,1..n] of integer; tyar:array of integer; i,j,max:integer;begin randomize; max:=integer.MinValue; writeln('Matrix:'); for i:=1 to n do begin for j:=1 to n do begin ma[i,j]:=random(100); write(ma[i,j]:4); if ma[i,j]>max then begin max:=ma[i,j]; setlength(tyar,max+1); inc(tyar[max]); end else inc(tyar[ma[i,j]]); end;

---

writeln; end; if tyar.Max=1 then writeln('-1') else writeln(tyar.IndexMax);end.

---

Когда вернусь с русского попытаюсь довести до ума.

---

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

Answer 1

Можно воспользоваться преимуществами, которые дает Pascal 3.1 и программа будет достаточно короткой.

// PascalABC.NET 3.1, сборка 1250 от 28.05.2016
begin
  var m:=ReadInteger('m=');
  var c:=MatrixRandom(m,m,10,99);
  var d:=new Dictionary;
  for var i:=0 to m-1 do begin
    for var j:=0 to m-1 do Print(c[i,j]);
    Println;
    end;
  foreach var e in c do d[e]:=d.Get(e)+1;
  var q:=d.OrderByDescending(x->x.Value);
  var p:=q.First.Value;
  if p=1 then Writeln('Все значения в массиве уникальны')
  else begin
    var s:=q.TakeWhile(x->x.Value=p).Select(x->x.Key);  
    Write('Наиболее часто (',p,') ');
    if s.Count=1 then begin
      Print('встречается значение');
      s.Print
      end
    else begin
      Print('встречаются значения:');
      s.Println
      end
    end
end.

Тестовые решения

m= 3
76 34 96
47 99 79
94 33 11
Все значения в массиве уникальны

m= 5
43 19 46 70 51
73 46 50 18 25
19 10 32 83 81
32 46 81 23 84
27 91 84 79 28
Наиболее часто (3) встречается значение 46

m= 10
89 11 84 46 18 68 56 13 28 34
86 25 84 34 51 13 37 41 26 23
33 74 87 21 11 42 61 42 32 65
34 37 47 23 24 20 61 14 93 31
71 27 19 31 81 94 38 87 74 83
19 74 81 28 70 24 23 72 44 76
17 24 80 62 10 58 78 71 19 40
52 33 48 94 51 16 64 65 40 16
13 74 68 48 56 60 56 28 53 99
97 88 69 27 23 57 46 57 31 33
Наиболее часто (4) встречаются значения: 23 74

Answer 2

{Attention! Это самое отвратное моё решение на Знаниях. Запаситесь валерьянкой перед прочтением кода}
//Pascal ABC.NET 3.1 сборка 1219

Type
 ty=record
 valu:integer;
 count:integer;
end;

Const
 n=3;

 Var
 ma:array[1..n,1..n] of integer;
 tyar:array of ty;
 se:set of integer;
 i,j,z,k,MaxCount:integer;
begin
 randomize;
 se:=[];
 k:=0;
 MaxCount:=integer.MinValue;
 writeln('Matrix:');
 for i:=1 to n do
  begin
   for j:=1 to n do
    begin
     ma[i,j]:=random(-10,10);
     write(ma[i,j]:4);
     if not(ma[i,j] in se) then
       begin
       inc(k);
       setlength(tyar,k+1);
       tyar[k].valu:=ma[i,j];
       tyar[k].count:=1;
       se:=se+[ma[i,j]];
      end
     else
       for z:=1 to k do {O(n^3) в худшем случае - нормальные люди ненавидят это}
        if tyar[z].valu=ma[i,j] then
         begin
          inc(tyar[z].count);
          break;
         end;
    end;
   writeln;
  end;
  for i:=1 to k do
  if MaxCount  writeln('Res:');
  for i:=1 to k do  if tyar[i].count=MaxCount then writeln(tyar[i].valu);
end.

Пример работы программы:
Matrix:
  -7  -2  10
   8   0  -2
   6  10   1
Res:
-2
10

Comments

Да... эпический подвиг)))