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{-}\text{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^2)\). 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 \in \mathbb{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 \in \mathbb{Z}}\).
\(L\) : licznik wystąpień wartości elementu, \({L \in \mathbb{Z}}\).
\(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 \in \mathbb{Z}}\).

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

JavaScript

<html>
  <head>
    <title>
      Najczęstsza wartość
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>&nbsp;&nbsp;
          Najczęstsza wartość
          w zbiorze
          &nbsp;&nbsp;</b><br/>
          (C)2026 mgr
          Jerzy Wałaszek
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

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

function main()
{
  let N = 400;
  let Z = Array(N);
  let c,i,j,L,W,maxL,maxW;

  // Generujemy zawartość Z[]
  for(i = 0; i < N; i++)
    Z[i] = Math.floor(
           Math.random() * 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;
    }
  }

  // Wyświetlamy wyniki
  t = "<table border='0' " +
      "cellspacing='0' " +
      "cellpadding='4'>"
  for(i = 0; i < 20; i++)
  {
    t += "<tr>";
    for(j = 0; j < 20; j++)
    {
      t += "<td style=" +
           "'text-align: right;'";
      L = 20 * i+j;
      if(Z[L] == maxW)
        t += "<span style=" +
             "'color:Red'>" +
             "<b>" + Z[L] +
             "</b></span>";
      else t += Z[L];
      t += "</td>";
    }
    t += "</tr>";
  }
  t += "</table><br/>" +
       maxW + " : " + maxL;
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

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{-}\text{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_L\) mamy 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 \in \mathbb{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 \in \mathbb{Z}}\).
\(L\) : licznik wystąpień wartości elementu; \({L \in \mathbb{Z}}\).
\(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 \in \mathbb{Z}}\).

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 \in \mathbb{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 \in \mathbb{Z}}\).
\(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 \in \mathbb{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:

Elementy pomocnicze:

\(i\) : przebiega przez kolejne indeksy elementów \(Z\); \({i \in \mathbb{Z}}\).
\(max_L\) : liczba wystąpień najczęstszego elementu w \(Z\); \({max_L \in \mathbb{Z}}\).
\(max_W\) : wartość najczęstszego elementu w \(Z\).
\(L\) : licznik równych elementów; \({L \in \mathbb{Z}}\).

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