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.

Zmienne 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: wykonuj kroki K03...K09	przeglądamy kolejne elementy tablicy Z
K03:	W ← Z [ i ]	zapamiętujemy poszukiwaną wartość elementu
K04:	L ← 0	zerujemy jej licznik wystąpień
K05:	Dla j = 0, 1, ..., n - 1: wykonuj krok K06	zliczamy wystąpienia W
K06:	Jeśli Z [ j ] = W, to L ← L + 1
K07:	Jeśli L ≤ max_L, to następny obieg pętli K2	sprawdzamy, czy W jest tymczasowo najczęstsze
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ę 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 <time.h>

using namespace std;

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

// Generujemy zawartość Z [ ] 

  srand ( ( unsigned )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ę 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ę wystąpień

Print
Print maxW;": ";maxL
Print
End

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

Na początek: podrozdziału 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_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 ∈ 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.

Zmienne 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, wykonuj kroki K05...K13	zliczamy do n-max_L
K05:	W ← Z [ i ]	zapamiętujemy wartość bieżącego elementu
K06:	Jeśli W = max_W, to idź do kroku K13	jeśli jest równa max_W, to pomijamy element Z [ i ]
K07:	L ← 1	Z [ i ] raz zliczony
K08:	Dla j = i + 1, i + 2, ..., n - 1: wykonuj krok K09	zliczanie rozpoczynamy od następnych elementów
K09:	Jeśli Z [ j ] = W, to L ← L + 1
K10:	Jeśli L ≤ max_L, to idź do kroku K13	zliczyliśmy więcej niż max_L?
K11:	max_L ← L	jeśli tak, zapamiętujemy L w max_L
K12:	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.

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; 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ę 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 <time.h>

using namespace std;

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

// Generujemy zawartość Z [ ] 

  srand ( ( unsigned )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ę 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ę wystąpień

Print
Print maxW;": ";maxL
Print
End

Na początek: podrozdziału 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ą ).

Zmienne 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: wykonuj krok K04	zliczamy wystąpienia wartości elementów
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 <time.h>

using namespace std;

const int N = 80;

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

  srand ( ( unsigned )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

Wynik:

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

Na początek: podrozdziału 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.

Zmienne 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:

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

using namespace std;

const int N = 200;

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

  srand ( ( unsigned )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;
      }
    x = Z [ i ]; Z [ i ] = Z [ minp ]; Z [ minp ] = x;
  }

// 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

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

Na początek: podrozdziału strony

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:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

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

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 3

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

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 4

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

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy