Algorytmy i Struktury Danych - Wyszukiwanie najczęstszej wartości

Problem wyszukiwania najczęstszej wartości (ang. searching for the most frequent value), czyli tzw. dominanty zbioru, możemy rozwiązać na kilka różnych sposobów. Pierwszym, najprostszym podejściem jest metoda bezpośrednia – naiwna:

Przeglądamy kolejne elementy zbioru i zliczamy liczbę wystąpień ich wartości w zbiorze. Można to robić tak – zapamiętujemy i-ty element i ustawiamy licznik wystąpień na 0. Następnie przeglądamy cały zbiór i, jeśli trafimy na element o takiej samej wartości, to licznik zwiększamy o 1. Po wykonaniu tej operacji porównujemy zawartość licznika z tymczasową maksymalną liczbą wystąpień (na początku algorytmu jest ona ustawiana na 0). Jeśli stan licznika jest większy, to zapamiętujemy go w tymczasowej maksymalnej liczbie wystąpień oraz zapamiętujemy wyszukiwaną wartość elementu. Gdy przeglądniemy w ten sposób i zliczymy wystąpienia wartości wszystkich elementów w zbiorze Z, to otrzymamy element powtarzający się najczęściej oraz ilość tych powtórzeń.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu jest równa O(n²). Jeśli elementów jest niewiele (do około 5000) i szybkość działania nie gra istotnej roli, to rozwiązanie naiwne jest do przyjęcia – tak właśnie było w przypadku zadania maturalnego.

Algorytm wygląda następująco:

Algorytm znajdowania najczęstszej wartości – wersja nr 1

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica do wyszukania najczęstszego elementu. Elementy są liczbami całkowitymi. Indeksy od 0 do n-1.

Wyjście:

Element występujący najczęściej w Z oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm zwraca pierwszy z nich, który został napotkany w zbiorze.

Elementy pomocnicze:

i, j : przebiega przez kolejne indeksy elementów Z. i, j ∈ C.
L : licznik wystąpień wartości elementu, L ∈ C.
W : wartość elementu, której liczbę wystąpień w Z zliczamy.
max_W : najczęstsza wartość elementów tablicy Z.
max_L : liczba wystąpień wartości najczęstszej. max_L ∈ C.

Lista kroków:

K01: max_L ← 0 ; zerujemy maksymalną liczbę wystąpień
K02: Dla i = 0, 1, …, n-1: ; przeglądamy kolejne elementy tablicy Z
     wykonuj kroki K03…K09
K03:   W ← Z[i] ; zapamiętujemy poszukiwaną wartość elementu
K04:   L ← 0 ; zerujemy jej licznik wystąpień
K05:   Dla j = 0, 1, …, n-1: ; zliczamy wystąpienia W
       wykonuj krok K06
K06:   Jeśli Z[j] = W, 
       to L ← L+1
K07:   Jeśli L ≤ max_L, ; sprawdzamy, czy W jest tymczasowo najczęstsze
       to następny obieg pętli K2
K08:   max_L ← L ; jeśli tak, zapamiętujemy liczbę wystąpień
K09:   max_W ← W ; oraz wartość W
K10: Pisz max_W, max_L; wypisujemy wyniki
K11: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program umieszcza w tablicy Z 400 liczb pseudolosowych z zakresu od 0 do 99, wyznacza wartość występującą najczęściej, wyświetla zawartość tej tablicy zaznaczając wartości najczęstsze i wypisuje tę wartość oraz liczbę jej wystąpień.

Pascal

// Najczęstsza wartość
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 400;

var
  Z : array [0..N-1] of integer;
  i, j, L, W, maxL, maxW : integer;

begin

  // Generujemy zawartość Z[]
  randomize;
  for i := 0 to N-1 do
    Z[i] := random(100);

  // Wyszukujemy najczęstszą wartość
  maxL := 0;
  for i := 0 to N-1 do
  begin
    W := Z[i]; L := 0;
    for j := 0 to N-1 do
      if Z[j] = W then
        inc(L);
    if L > maxL then
    begin
      maxL := L; maxW := W;
    end;
  end;

  // Wypisujemy tablicę
  for i := 0 to N-1 do
    if Z[i] = maxW then
      write(' >', Z[i]:2)
    else
      write(Z[i]:4);

  // Wypisujemy najczęstszy element
  // oraz liczbę jego wystąpień
  writeln;
  writeln(maxW, ' : ', maxL);
  writeln;

end.

C++

// Najczęstsza wartość
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  const int N = 400;
  int Z[N], i, j, L, W, maxL, maxW;

  // Generujemy zawartość Z[]
  srand (time(NULL));
  for(i = 0; i < N; i++)
    Z[i] = rand() % 100;

  // Wyszukujemy najczęstszą wartość
  maxL = 0;
  for(i = 0; i < N; i++)
  {
    W = Z[i]; L = 0;
    for(j = 0; j < N; j++)
      if(Z[j] == W) L++;
    if(L > maxL)
    {
      maxL = L; maxW = W;
    }
  }

  // Wypisujemy tablicę
  for(i = 0; i < N; i++)
    if(Z[i] == maxW)
      cout << " >" << setw(2) << Z[i];
    else
      cout << setw(4) << Z[i];

  // Wypisujemy najczęstszy element
  // oraz liczbę jego wystąpień
  cout << endl << maxW << ": " << maxL
       << endl << endl;
  return 0;
}

Basic

' Najczęstsza wartość
' Data:   4.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 400

Dim As Integer Z(N-1)
Dim As Integer i, j, L, W, maxL, maxW

' Generujemy zawartość Z()
Randomize
For i = 0 To N-1
  Z(i) = Cint(Rnd*99)
Next

' Wyszukujemy najczęstszą wartość
maxL = 0
For i = 0 To N-1
  W = Z(i): L = 0
  For j = 0 To N-1
    If Z(j) = W Then L += 1
  Next
  If L > maxL Then
    maxL = L: maxW = W
  End If
Next

' Wypisujemy tablicę
For i = 0 To N-1
  If Z(i) = maxW Then
    Print Using " >##";Z(i);
  Else
    Print Using "####";Z(i);
  End If
Next

' Wypisujemy najczęstszy element
' oraz liczbę jego wystąpień
Print
Print maxW;": ";maxL
Print
End

Python (dodatek)

# Najczęstsza wartość
# Data:  26.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 400
z = []

# Generujemy zawartość Z()
for i in range(N):
    z.append(random.randrange(100))
# Wyszukujemy najczęstszą wartość
maxv, maxc = 0, 0
for i in range(N):
    v, c = z[i], 0
    for j in range(N):
        if z[j] == v:
            c += 1
    if c > maxc:
        maxc, maxv = c, v
# Wypisujemy tablicę
for i in range(N):
    if z[i] == maxv:
        print(" >%2d" % z[i], end="")
    else:
        print("%4d" % z[i], end="")
# Wypisujemy najczęstszy element
# oraz liczbę jego wystąpień
print()
print(maxv, ":", maxc)
print()

Wynik:

  21  84  16  62  83  81   6  92  96 >85  18  72  70  96   8  37  23  91  74  99
  87  14  33  20  58  25  42  55  41   3  91  23  38  98  42  91  51  35  31  39
  65  17  46   5  89 >85  39   5  60 >85  30  36  60  80  73   9   6  90  55  51
   5  84  25  75  16  71  39 >85  70   6   6  72  30  93  55  93  67   6  35  35
  48  18  65  25  50  11  17  90  15  30  84  82  64   5  50  74  47  11  10  92
  79   0   6   1  75  79  65  11  33  22  86  24  61  96  12  46  29  82  23  62
  35  36  39  26  59  46  97  57  29  58  69  86  27  28  17  81  55  38  26  45
  76  39  16  71  78  29  49  42   6  38  24  25  45  52  89  49  52  36  92  79
  49  26  57  86  11  17  67  93  96  29  96  16  79  36  70  19  11  20  60  46
  43 >85  25  90  11  96   1  92  80  20  60   1  13  30  72  80 >85  47  87  67
  29  90  20  98  47   6  95  60  19  77  90  22  13  52  23  50  54  45  29  50
   4  21  60  56  75  59  94   5  88 >85  15  49   5  77  64  62  71  82  32  42
  59  35   8  45  44  52  71   7  12  79  58  29   9   7  90 >85  87  68  65  38
  32   0  55  12  56  76  97  58  24  91  97  62  49  34  49  96   6  18  44  15
  50   3  32  13  67  16  38  69  89  66  73  84  82  57  68  65  89  19  49  33
  34  94  13  27  19   5  49  59  82  21  25  38  49  94 >85  45  48  63  53   2
   1  70  37  13  89  51  44  20  24  46  74  89   2  11  87  28  83  30  23  81
  64  27  15  81  95  93  71  29  47  45  17  64  90  77   1  73  61  26  79  47
  91  82  17  88  26  22  57  63  12  14  43  74  31  40  50  28  36  61  77  77
  15  19  41  71  23  24   3  33  32  65  30  97 >85  38  62  87  82  65  53  24

85 : 10

do podrozdziału do strony

Podany powyżej algorytm jest bardzo prymitywny i wykonuje wiele niepotrzebnych działań. Postarajmy się je wyeliminować.

Ze zbioru bierzemy KAŻDY element Z[i] i zliczamy wystąpienia jego wartości W w CAŁYM zbiorze Z. W ten sposób najczęstsza wartość max_W zostanie zliczona max_L² razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element W zbioru zliczamy tylko wtedy, gdy jest on różny od max_W. Wynika z tego, iż na początku pracy algorytmu do max_W musimy wpisać wartość różną od Z[0] (dlaczego?).
Każdy element Z[i] zliczamy w całym zbiorze. Tymczasem, jeśli wartość i-tego elementu wystąpiła wcześniej w zbiorze, to jest już zliczona. Jeśli nie wystąpiła wcześniej, to nie ma sensu jej tam szukać, nieprawdaż? W obu przypadkach wystarczy, jeśli zliczanie rozpoczniemy od pozycji i+1 do końca zbioru. Elementy zliczone po prostu zliczymy ponownie, lecz w mniejszym zakresie. Elementy nowe zliczymy poprawnie, od miejsca ich pierwszego wystąpienia.
Jeśli w trakcie działania algorytmu w max_Lmamy chwilową maksymalną liczbę wystąpień pewnej wartości max_W, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n-max_L. Jeśli nowy element występuje na tej lub dalszej pozycji w zbiorze Z, to liczba wystąpień jego wartości nie będzie już większa od max_L, gdyż braknie elementów.

Algorytm znajdowania najczęstszej wartości – wersja nr 2

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n-1.

Wyjście:

Elementy pomocnicze:

i, j : przebiega przez kolejne indeksy elementów Z. i, j ∈ C.
L : licznik wystąpień wartości elementu, L ∈ C.
W : wartość elementu, której liczbę wystąpień w Z zliczamy.
max_W : najczęstsza wartość elementów tablicy Z.
max_L : liczba wystąpień wartości najczęstszej. max_L ∈ C.

Lista kroków:

K01: max_L ← 0 ; licznik wystąpień najczęstszej wartości
K02: max_W ← Z[0]-1 ; najczęstsza wartość-musi być różna od Z[0]!
K03: i ← 0 ; rozpoczynamy zliczanie wartości elementów
K04: Dopóki i < n-max_L, ; zliczamy do n-max_L
     wykonuj kroki K05…K13
K05:   W ← Z[i] ; zapamiętujemy wartość bieżącego elementu
K06:   Jeśli W = max_W, ; jeśli jest równa max_W, 
       to idź do kroku K13 ; to pomijamy element Z[i]
K07:   L ← 1 ; Z[i] raz zliczony
K08:   Dla j = i+1, i+2, …, n-1: ; zliczanie rozpoczynamy
       wykonuj krok K09 ; od następnych elementów
K09:     Jeśli Z[j] = W, 
         to L ← L+1
K10:   Jeśli L ≤ max_L, ; zliczyliśmy więcej niż max_L?
       to idź do kroku K13
K11:   max_L ← L ; jeśli tak, zapamiętujemy L w max_LK12:   max_W ← W ; oraz W w max_W
K13:   i ← i+1 ; przechodzimy do kolejnego elementu Z[i]
K14: Pisz max_W, max_L; wyprowadzamy wyniki
K15: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Pascal

// Najczęstsza wartość
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 400;

var
  Z : array [0..N-1] of integer;
  i, j, L, W, maxL, maxW : integer;

begin

  // Generujemy zawartość Z[]
  randomize;
  for i := 0 to N-1 do
    Z[i] := random(100);

  // Wyszukujemy najczęstszą wartość
  maxL := 0; maxW := Z[0]-1;
  i := 0;
  while i < N-maxL do
  begin
    W := Z[i];
    if maxW <> W then
    begin
      L := 1;
      for j := i+1 to N-1 do
        if Z[j] = W then inc(L);
      if L > maxL then
      begin
        maxL := L; maxW := W;
      end;
    end;
    inc(i);
  end;

  // Wypisujemy tablicę Z[]
  for i := 0 to N-1 do
    if Z[i] = maxW then
      write(' >', Z[i]:2)
    else
      write(Z[i]:4);

  // Wypisujemy najczęstszy element
  // oraz liczbę jego wystąpień
  writeln;
  writeln(maxW, ' : ', maxL);
  writeln;

end.

C++

// Najczęstsza wartość
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  const int N = 400;
  int Z[N], i, j, L, W, maxL, maxW;

  // Generujemy zawartość Z[]
  srand(time(NULL));
  for(i = 0; i < N; i++)
    Z[i] = rand() % 100;

  // Wyszukujemy najczęstszą wartość
  maxL = 0; maxW = Z[0]-1;
  for(i = 0; i < N-maxL; i++)
  {
    W = Z[i];
    if(maxW != W)
    {
      L = 1;
      for(j = i+1; j < N; j++)
        if(Z[j] == W) L++;
      if(L > maxL)
      {
        maxL = L; maxW = W;
      }
    }
  }

  // Wypisujemy tablicę
  for(i = 0; i < N; i++)
    if(Z[i] == maxW)
      cout << " >" << setw(2) << Z[i];
    else
      cout << setw(4) << Z[i];

  // Wypisujemy najczęstszy element
  // oraz liczbę jego wystąpień
  cout << endl
       << maxW << ": " << maxL
       << endl << endl;
  return 0;
}

Basic

' Najczęstsza wartość
' Data:   4.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 400

Dim As Integer Z(N-1)
Dim As Integer i, j, L, W, maxL, maxW

' Generujemy zawartość Z()
Randomize
For i = 0 To N-1
  Z(i) = Cint(Rnd*99)
Next

' Wyszukujemy najczęstszą wartość
maxL = 0: maxW = Z(0)-1
i = 0
While i < N-maxL
  W = Z(i)
  If maxW <> W Then
    L = 1
    For j = i+1 To N-1
      If Z(j) = W Then L += 1
    Next
    If L > maxL Then
      maxL = L: maxW = W
    End If
  End If
  i += 1
Wend

' Wypisujemy tablicę
For i = 0 To N-1
  If Z(i) = maxW Then
    Print Using " >##";Z(i);
  Else
    Print Using "####";Z(i);
  End If
Next

' Wypisujemy najczęstszy element
' oraz liczbę jego wystąpień
Print
Print maxW;": ";maxL
Print
End

Python (dodatek)

# Najczęstsza wartość
# Data: 25.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 400 # Liczba elementów

# Generujemy zawartość Z[]
z = [random.randrange(100) for i in range(N)]

# Wyszukujemy najczęstszą wartość
maxc = 0
maxv = z[0]-1
i = 0
while i < N-maxc:
    v = z[i];
    if maxv != v:
        c = 1;
        for j in range(i+1, N):
            if z[j] == v:
                c += 1
        if c > maxc:
            maxc, maxv = c, v
    i += 1
# Wypisujemy tablicę
for i in range(N):
    if z[i] == maxv:
        print(" >%2d" % z[i], end="")
    else:
        print("%4d" % z[i], end="")
print()
print()
# Wypisujemy najczęstszy element
# oraz liczbę jego wystąpień
print(maxv, ":", maxc)

do podrozdziału do strony

Jeśli elementy zbioru tworzą spójny przedział wartości i przedział ten nie jest specjalnie duży, to do wyszukania wartości najczęstszej można zastosować następującą metodę.

Tworzymy tablicę L, której elementy będą pełniły rolę liczników wystąpień wartości elementów z tablicy Z. Zakres indeksów w L możemy znaleźć wyszukując w tablicy Z wartość minimalną i maksymalną (można też z góry przydzielić odpowiednią liczbę liczników, gdy znamy zakres wartości elementów w przeszukiwanej tablicy Z). Zerujemy wszystkie liczniki w L i przeglądamy tablicę Z zwiększając o 1 liczniki w L, które odpowiadają wartościom przeglądanych elementów. W efekcie po zakończeniu przeglądania tablicy Z w L będziemy mieli informację o liczbie wystąpień każdej z wartości. Wyznaczamy w L element maksymalny. Wynikiem jest indeks, który określa wartość występującą najczęściej w Z oraz zawartość elementu L o tym indeksie, która określa, ile razy dana wartość wystąpiła w Z.

Tak określony algorytm wyszukiwania najczęstszego elementu posiada liniową klasę złożoności obliczeniowej O(m+n), gdzie m jest liczbą wartości elementów przeszukiwanego zbioru, a n jest liczbą jego elementów.

Algorytm znajdowania najczęstszej wartości – wersja nr 3

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica do wyszukania najczęstszego elementu. Elementy są liczbami całkowitymi. Indeksy od 0 do n-1.
min_Z : minimalna wartość w Z.
max_Z : maksymalna wartość w Z.

Wyjście:

Element występujący najczęściej w Z oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm w tej wersji zwraca najmniejszy z nich (jeśli pozostałe elementy są istotne, to można je odczytać z tablicy L porównując liczbę wystąpień z maksymalną).

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
L : tablica liczników wystąpień wartości elementów z Z.
max_L : tymczasowy element maksymalny w L.
max_p : pozycja tymczasowego elementu maksymalnego w L.

Lista kroków:

K01: Utwórz L o rozmiarze max_Z-min_Z+1 ; przygotowujemy liczniki wartości
K02: Wyzeruj L ; liczniki ustawiamy na 0
K03: Dla i = 0, 1, …, n-1: ; zliczamy wystąpienia wartości elementów
     wykonuj krok K04
K04: Zwiększ o 1 L[Z[i]-min_Z ; w odpowiednich licznikach
K05: max_L ← L[0] ; szukamy max w L
K06: max_p ← 0
K07: Dla i = 1, 2, …, max_Z-min_Z:
     wykonuj kroki K08…K10
K08:   Jeśli L[i] ≤ max_L, 
       to następny obieg pętli K07
K09:   max_L ← L[i] ; zapamiętujemy wartość maksymalną
K10:   max_p ← i ; oraz jej pozycję
K11: Pisz max_p+min_Z, max_L ; wyprowadzamy najczęstszy element
                        ; oraz liczbę jego wystąpień
K12: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program umieszcza w tablicy Z 80 liczb pseudolosowych z zakresu od -9 do 9, wyświetla zawartość tej tablicy i wyznacza w niej wartość występującą najczęściej. Program wypisuje tę wartość oraz liczbę jej wystąpień w tablicy Z.

Pascal

// Najczęstsza wartość
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 80;

type Tint = array of integer;

var
  Z : array [0..N-1] of integer;
  L : Tint;
  i, nL, maxZ, minZ, maxL, maxp : integer;

begin

  randomize;

  // Przygotowujemy tablicę Z[]
  for i := 0 to N-1 do
    Z[i] := -9+random(19);

  // Wyświetlamy tablicę Z[]
  for i := 0 to N-1 do
    write(Z[i]:4);

  // Wyszukujemy w Z[] min i max
  if Z[0] > Z[1] then
  begin
    minZ := Z[1]; maxZ := Z[0];
  end
  else
  begin
    minZ := Z[0]; maxZ := Z[1];
  end;
  i := 2;
  while i < N do
  begin
    if Z[i] > Z[i+1] then
    begin
      if Z[i] > maxZ then
        maxZ := Z[i];
      if Z[i+1] < minZ then
        minZ := Z[i+1];
    end
    else
    begin
      if Z[i] < minZ then
        minZ := Z[i];
      if Z[i+1] > maxZ then
        maxZ := Z[i+1];
    end;
    inc(i, 2);
  end;

  // Przygotowujemy liczniki
  nL := maxZ-minZ+1;
  SetLength(L, nL);
  for i := 0 to nL-1 do
    L[i] := 0;

  // Zliczamy wystąpienia wartości z Z[]
  for i := 0 to N-1 do
    inc(L[Z[i]-minZ]);

  // Szukamy najczęstszej wartości w L[]
  maxL := L[0]; maxp := 0;
  for i := 0 to nL-1 do
    if L[i] > maxL then
    begin
      maxL := L[i]; maxp := i;
    end;

  // Wyświetlamy wyniki
  writeln;
  writeln(maxp+minZ, ' : ', maxL);
  writeln;
end.

C++

// Najczęstsza wartość
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 80;

int main()
{
  int Z[N], *L, i, nL, maxZ, minZ, maxL, maxp;

  srand(time(NULL));

  // Przygotowujemy tablicę Z[]
  for(i = 0; i < N; i++)
    Z[i] = -9+(rand() % 19);

  // Wyświetlamy tablicę Z[]
  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];

  // Wyszukujemy w Z[] min i max
  if(Z[0] > Z[1])
  {
    minZ = Z[1]; maxZ = Z[0];
  }
  else
  {
    minZ = Z[0]; maxZ = Z[1];
  }
  for(i = 2; i < N; i += 2)
  {
    if(Z[i] > Z[i+1])
    {
      if(Z[i]   > maxZ) maxZ = Z[i];
      if(Z[i+1] < minZ) minZ = Z[i+1];
    }
    else
    {
      if(Z[i]   < minZ) minZ = Z[i];
      if(Z[i+1] > maxZ) maxZ = Z[i+1];
    }
  }

  // Przygotowujemy liczniki
  nL = maxZ-minZ+1;
  L = new int[nL];
  for(i = 0; i < nL; i++) L[i] = 0;

  // Zliczamy wystąpienia wartości z Z[]
  for(i = 0; i < N; i++)
    L[Z[i]-minZ]++;

  // Szukamy najczęstszej wartości w L[]
  maxL = L[0]; maxp = 0;
  for(i = 0; i < nL; i++)
    if(L[i] > maxL)
    {
      maxL = L[i]; maxp = i;
    }

  // Wyświetlamy wyniki
  cout << endl
       << (maxp+minZ) << " : " << maxL
       << endl << endl;
  delete [] L;
  return 0;
}

Basic

' Najczęstsza wartość
' Data:   1.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 80

Dim As Integer Z(N-1), i, nL, maxZ, minZ, maxL, maxp

Randomize

' Przygotowujemy tablicę Z()
For i = 0 To N-1
  Z(i) = -9+Cint(Rnd*18)
Next

' Wyświetlamy tablicę Z()
For i = 0 To N-1
  Print Using "####";Z(i);
Next

' Wyszukujemy w Z() min i max
If Z(0) > Z(1) Then
  minZ = Z(1): maxZ = Z(0)
Else
  minZ = Z(0): maxZ = Z(1)
End If
i = 2
While i < N
  If Z(i) > Z(i+1) Then
    If Z(i)   > maxZ Then maxZ = Z(i)
    If Z(i+1) < minZ Then minZ = Z(i+1)
  Else
    If Z(i)   < minZ Then minZ = Z(i)
    If Z(i+1) > maxZ Then maxZ = Z(i+1)
  End If
  i += 2
Wend

' Przygotowujemy liczniki
nL = maxZ-minZ+1
Dim As Integer L(nL-1)
For i = 0 To nL-1: L(i) = 0: Next

' Zliczamy wystąpienia wartości z Z()
For i = 0 To N-1
  L(Z(i)-minZ) += 1
Next

' Szukamy najczęstszej wartości w L()
maxL = L(0): maxp = 0
For i = 0 To nL-1
  If L(i) > maxL Then
    maxL = L(i): maxp = i
  End If
Next

' Wyświetlamy wyniki
Print
Print maxp+minZ;" : ";maxL
Print
End

Python (dodatek)

# Najczęstsza wartość
# Data:  25.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 80  # Ilość liczb
z = []  # Tablica

# Przygotowujemy i wyświetlamy tablicę Z[]
for i in range(N):
    z.append(random.randrange(-9, 10))
    print("%4d" % z[i], end="")
# Wyszukujemy w Z[] min i max
if z[0] > z[1]:
    minz, maxz = z[1], z[0]
else:
    minz, maxz = z[0], z[1]
for i in range(2, N, 2):
    if z[i] > z[i+1]:
        if z[i] > maxz:
            maxz = z[i]
        if z[i+1] < minz:
            minz = z[i+1]
    else:
        if z[i] < minz:
            minz = z[i]
        if z[i+1] > maxz:
            maxz = z[i+1]
# Przygotowujemy liczniki
nc = maxz-minz+1
c = [0]*nc
# Zliczamy wystąpienia wartości z Z[]
for i in range(N):
    c[z[i]- minz] += 1
# Szukamy najczęstszej wartości w c[]
maxc, maxp = c[0], 0
for i in range(nc):
    if c[i] > maxc:
        maxc, maxp = c[i], i
# Wyświetlamy wyniki
print()
print(maxp+minz, ":", maxc)
print()

Wynik:

  -7  -9  -1   0   4   2   7  -1  -4   9   2   1   8  -3  -6   2   0   3   2   0
   1  -7  -7  -9  -6   7  -4  -2  -2   8   2   0  -4  -3   0   4  -4   2   4   8
  -3   6  -9  -4   2  -3   2  -4  -6   7  -2   7  -4  -5  -1  -4  -5  -2   6  -7
   7   2   9   4  -4   8  -3   6  -7   3   2  -8   3  -4  -3   7   7  -7   9   3

-4 : 10

do podrozdziału do strony

Zbiór Z możemy posortować rosnąco. Wtedy elementy o równych wartościach znajdą się obok siebie. Teraz wystarczy przeglądnąć zbiór Z od początku do końca, zliczać powtarzające się wartości i zapamiętać tę wartość, która powtarza się najczęściej. Klasa złożoności obliczeniowej algorytmu w tej wersji zależy od zastosowanego algorytmu sortującego zbiór Z. Samo przeglądnięcie zbioru i wyłonienie najczęstszej wartości ma liniową klasę złożoności obliczeniowej O(n).

Zaletą tego algorytmu jest to, iż elementy tablicy Z nie muszą być koniecznie liczbami całkowitymi. Mogą to być obiekty dowolnego typu.

Algorytm znajdowania najczęstszej wartości – wersja nr 4

Wejście:

n : liczba elementów w tablicy Z, n ∈ N.
Z : tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n. Tablica powinna być posortowana rosnąco. Na końcu tablicy – element Z[n] – powinien być umieszczony wartownik o wartości innej niż wartość ostatniego elementu – Z[n-1].

Wyjście:

Element występujący najczęściej w Z oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm w tej wersji zwraca najmniejszy z nich.

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
max_L : liczba wystąpień najczęstszego elementu w Z, max_L∈ C.
max_W : wartość najczęstszego elementu w Z.
L : licznik równych elementów, L ∈ C.

Lista kroków:

K01: max_L ← 0 ; inicjujemy liczbę wystąpień na 0
K02: L ← 1 ; w L zliczamy pierwszy element
K03: Dla i = 1, 2, …, n: ; przeglądamy kolejne elementy 
     wykonuj kroki K04…K09 ; aż do wartownika
K04:   Jeśli Z[i] = Z[i-1], ; dla równych elementów 
       to idź do kroku K09 ; zwiększamy L o 1
K05:   Jeśli L ≤ max_L, ; elementy nie są równe, 
       to idź do kroku K08 ; sprawdzamy licznik L
K06:   max_L ← L ; jeśli L > max_L, to zapamiętujemy L
K07:   max_W ← Z[i-1] ; oraz wartość elementu
K08:   L ← 0 ; dla nowego elementu licznik L wystartuje od 1
K09:   L ← L+1 ; zliczamy elementy równe
K10: Pisz max_W, max_L ; wypisujemy wyniki
K11: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program umieszcza w tablicy Z 200 liczb pseudolosowych z zakresu od 0 do 9, sortuje tablicę algorytmem sortowania przez wybór, wyświetla ją oraz wyznacza najczęstszą wartość. Program wyświetla tę wartość oraz liczbę jej wystąpień.

Pascal

// Najczęstsza wartość
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 200;

var
  Z : array [0..N] of integer;
  maxL, maxW, minZ, minp, L, i, j, x : integer;

begin
  randomize;

  // Inicjujemy tablicę Z[]
  for i := 0 to N-1 do
    Z[i] := random(10);

  // Sortujemy tablicę Z[]
  for i := 0 to N-2 do
  begin
    minZ := Z[i];
    minp := i;
    for j := i+1 to N-1 do
      if Z[j] < minZ then
      begin
        minZ := Z[j];
        minp := j;
      end;
    x := Z[i];
    Z[i] := Z[minp];
    Z[minp] := x;
  end;

  // Wyświetlamy tablicę Z[]
  for i := 0 to N-1 do
    write(Z[i]:2);
  writeln;

  // Dodajemy wartownika
  Z[N] := Z[N-1]-1;

  // Szukamy najczęstszej wartości
  maxL := 0; L := 1;
  for i := 1 to N do
  begin
    if Z[i] <> Z[i-1] then
    begin
      if L > maxL then
      begin
        maxL := L;
        maxW := Z[i-1];
      end;
      L := 0;
    end;
    inc(L);
  end;

  // Wyświetlamy wyniki
  writeln(maxW, ' : ', maxL);
  writeln;
end.

C++

// Najczęstsza wartość
// Data:   1.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 200;

int main()
{
  int Z[N+1], maxL, maxW, minZ, minp, L, i, j;

  srand(time(NULL));

  // Inicjujemy tablicę Z[]
  for(i = 0; i < N; i++)
    Z[i] = rand() % 10;

  // Sortujemy tablicę Z[]
  for(i = 0; i < N-1; i++)
  {
    minZ = Z[i]; minp = i;
    for(j = i+1; j < N; j++)
      if(Z[j] < minZ)
      {
        minZ = Z[j]; minp = j;
      }
    swap(Z[i], Z[minp]);
  }

  // Wyświetlamy tablicę Z[]
  for(i = 0; i < N; i++)
    cout << setw(2) << Z[i];
  cout << endl;

  // Dodajemy wartownika
  Z[N] = Z[N-1]-1;

  // Szukamy najczęstszej wartości
  maxL = 0; L = 1;
  for(i = 1; i <= N; i++)
  {
    if(Z[i] != Z[i-1])
    {
      if(L > maxL)
      {
        maxL = L; maxW = Z[i-1];
      }
      L = 0;
    }
    L++;
  }

  // Wyświetlamy wyniki
  cout << maxW << " : " << maxL
       << endl << endl;
  return 0;
}

Basic

' Najczęstsza wartość
' Data:   1.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 200

Dim As Integer Z(N), maxL, maxW, minZ, minp, L, i, j

Randomize

' Inicjujemy tablicę Z[]
For i = 0 To N-1
  Z(i) = Cint(Rnd*9)
Next

' Sortujemy tablicę Z[]
For i = 0 To N-2
  minZ = Z(i): minp = i
  For j = i+1 To N-1
    If Z(j) < minZ Then
      minZ = Z(j): minp = j
    End If
  Next
  Swap Z(i), Z(minp)
Next

' Wyświetlamy tablicę Z[]
For i = 0 To N-1
  Print Using "##";Z(i);
Next
Print

' Dodajemy wartownika
Z(N) = Z(N-1)-1

' Szukamy najczęstszej wartości
maxL = 0: L = 1
For i = 1 To N
  If Z(i) <> Z(i-1) Then
    If L > maxL Then
      maxL = L: maxW = Z(i-1)
    End If
    L = 0
  End If
  L += 1
Next

' Wyświetlamy wyniki
Print maxW;" : ";maxL
Print
End

Python (dodatek)

# Najczęstsza wartość
# Data:  26.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 200

# Inicjujemy tablicę Z[]
z = [random.randrange(10) for i in range(N)]
# Sortujemy tablicę Z[]
for i in range(N-1):
    minz, minp = z[i], i
    for j in range(i+1, N):
        if z[j] < minz:
            minz, minp = z[j], j
    z[i], z[minp] = z[minp], z[i]
# Wyświetlamy tablicę Z[]
for i in range(N):
    print("%2d" % z[i], end="")
print()
# Dodajemy wartownika
z.append(z[N-1]-1)
# Szukamy najczęstszej wartości
maxc, c = 0, 1
for i in range(1, N+1):
    if z[i] != z[i-1]:
        if c > maxc:
            maxc, maxv = c, z[i-1]
        c = 0
    c += 1
# Wyświetlamy wyniki
print(maxv, ":", maxc)
print()

Wynik:

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4
 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6
 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8
 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

8 : 28

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie najczęstszej wartości w zbiorze – dominanta

Problem

Rozwiązanie 1

Algorytm znajdowania najczęstszej wartości – wersja nr 1

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm znajdowania najczęstszej wartości – wersja nr 2

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 3

Algorytm znajdowania najczęstszej wartości – wersja nr 3

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 4

Algorytm znajdowania najczęstszej wartości – wersja nr 4

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy