Wyszukiwanie najczęstszej wartości w zbiorze – dominanta


Tematy pokrewne   Podrozdziały
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych
  Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3
Rozwiązanie 4

 

Problem

W n-elementowym zbiorze Z znaleźć 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 nr 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(n2). 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.
maxW  – najczęstsza wartość elementów tablicy Z
maxL  – liczba wystąpień wartości najczęstszej. maxL C
Lista kroków:
K01: maxL ← 0 ; zerujemy maksymalną liczbę wystąpień
K02: Dla i = 0,1,...,n - 1 wykonuj K03...K09 ; przeglądamy kolejne elementy tablicy Z
K03:     WZ[i] ; zapamiętujemy poszukiwaną wartość elementu
K04:     L ← 0 ; zerujemy jej licznik wystąpień
K05:     Dla j = 0,1,...,n - 1 wykonuj K06 ; zliczamy wystąpienia W
K06:         Jeśli Z[j] = W, to LL + 1  
K07:     Jeśli LmaxL, to następny obieg pętli K2 ; sprawdzamy, czy W jest tymczasowo najczęstsze
K08:     maxLL ; jeśli tak, zapamiętujemy liczbę wystąpień
K09:     maxWW ; oraz wartość W
K10: Pisz maxW, maxL ; wypisujemy wyniki
K11: Zakończ  

 

Program

Ważne:

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ń.

 

Lazarus
// Najczęstsza wartość
// Data:   4.05.2008
// (C)2012 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.
Code::Blocks
// Najczęstsza wartość
// Data:   4.05.2008
// (C)2012 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;
}
Free Basic
' Najczęstsza wartość
' Data:   4.05.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 

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ść maxW zostanie zliczona maxL2 razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element W zbioru zliczamy tylko wtedy, gdy jest on różny od maxW. Wynika z tego, iż na początku pracy algorytmu do maxW 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 maxL mamy chwilową maksymalną liczbę wystąpień pewnej wartości maxW, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n - maxL. 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 maxL, 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.
maxW  – najczęstsza wartość elementów tablicy Z
maxL  – liczba wystąpień wartości najczęstszej. maxL C
Lista kroków:
K01: maxL ← 0 ; licznik wystąpień najczęstszej wartości
K02: maxWZ[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 - maxL, wykonuj K05...K13 ; zliczamy do n-maxL
K05:     WZ[i] ; zapamiętujemy wartość bieżącego elementu
K06:     Jeśli W = maxW, to idź do K13 ; jeśli jest równa maxW, to pomijamy element Z[i]
K07:     L ← 1 ; Z[i] raz zliczony
K08:     Dla j = i+1,i+2,...,n-1 wykonuj K09 ; zliczanie rozpoczynamy od następnych elementów
K09:         Jeśli Z[j] = W, to LL + 1  
K10:     Jeśli LmaxL, to idź do K13 ; zliczyliśmy więcej niż maxL?
K11:     maxLL ; jeśli tak, zapamiętujemy L w maxL
K12:     maxWW ; oraz W w maxW
K13:     ii + 1 ; przechodzimy do kolejnego elementu Z[i]
K14: Pisz maxW,maxL ; wyprowadzamy wyniki
K15: Zakończ  

 

Program

Ważne:

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ń.

 

Lazarus
// Najczęstsza wartość
// Data:   4.05.2008
// (C)2012 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.
Code::Blocks
// Najczęstsza wartość
// Data:   4.05.2008
// (C)2012 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;
}
Free Basic
' Najczęstsza wartość
' Data:   4.05.2008
' (C)2012 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
Wynik
 

 

Rozwiązanie nr 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, n N
Z  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..
minZ  – minimalna wartość w Z.
maxZ  – 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.
maxL  – tymczasowy element maksymalny w L
maxp  – pozycja tymczasowego elementu maksymalnego w L
Lista kroków:
K01: Utwórz L o rozmiarze maxZ - minZ + 1 ; przygotowujemy liczniki wartości
K02: Wyzeruj L ; liczniki ustawiamy na 0
K03: Dla i = 0,1,...,n-1 wykonuj K04 ; zliczamy wystąpienia wartości elementów
K04:      Zwiększ o 1 L[Z[i] - minZ] ; w odpowiednich licznikach
K05: maxLL[0] ; szukamy max w L
K06: maxp ← 0  
K07: Dla i = 1,2,...,maxZ-minZ wykonuj K08...K10  
K08:     Jeśli L[i] ≤ maxL, to następny obieg pętli K07  
K09:     maxLL[i] ; zapamiętujemy wartość maksymalną
K10:     maxpi ; oraz jej pozycję
K11: Pisz maxp + minZ, maxL ; wyprowadzamy najczęstszy element oraz liczbę jego wystąpień
K12: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Najczęstsza wartość
// Data:   1.05.2008
// (C)2012 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.
Code::Blocks
// Najczęstsza wartość
// Data:   1.05.2008
// (C)2012 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;
}
Free Basic
' Najczęstsza wartość
' Data:   1.05.2008
' (C)2012 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

 

Rozwiązanie nr 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, 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
maxL  – liczba wystąpień najczęstszego elementu w Z, maxL C
maxW  – wartość najczęstszego elementu  w Z
L  – licznik równych elementów, L C
Lista kroków:
K02: maxL ← 0 ; inicjujemy liczbę wystąpień na 0
K03: L ← 1 ; w L zliczamy pierwszy element
K04: Dla i = 1,2,...,n wykonuj K05...K10 ; przeglądamy kolejne elementy aż do wartownika
K05:     Jeśli Z[i] = Z[i - 1], to idź do K10 ; dla równych elementów zwiększamy L o 1
K06:     Jeśli LmaxL, to idź do K09 ; elementy nie są równe, sprawdzamy licznik L
K07:     maxLL ; jeśli L > maxL, to zapamiętujemy L
K08:     maxWZ[i - 1] ; oraz wartość elementu
K09:     L ← 0 ; dla nowego elementu licznik L wystartuje od 1
K10:     LL + 1 ; zliczamy elementy równe
K11: Pisz maxW, maxL ; wypisujemy wyniki
K12: Zakończ  

 

Program

Ważne:

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ń.

 

Lazarus
// Najczęstsza wartość
// Data:   1.05.2008
// (C)2012 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.
Code::Blocks
// Najczęstsza wartość
// Data:   1.05.2008
// (C)2012 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;
}
Free Basic
' Najczęstsza wartość
' Data:   1.05.2008
' (C)2012 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

 

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.