Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie najczęstszej wartości w zbiorze – dominanta

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

W n-elementowym zbiorze Z  należy wyszukać wartość występującą najczęściej.


Zadanie o podobnej treści pojawiło się w zestawie pytań maturalnych z informatyki w 2006 roku.

Rozwiązanie 1

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 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, nN.
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, jC.
L  – licznik wystąpień wartości elementu, LC.
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 LC.

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
Najczęstsza wartość w zbiorze
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

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

  1. 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 2 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? ).
  2. 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.
  3. 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, nN.
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, jC.
L  – licznik wystąpień wartości elementu, LC.
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 LC.

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 

Rozwiązanie 3

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, nN.
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. iC.
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 

Rozwiązanie 4

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, nN.
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. iC.
max L  – liczba wystąpień najczęstszego elementu w Z, max LC.
max W  – wartość najczęstszego elementu  w Z.
L  – licznik równych elementów, LC.

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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.