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

©2024 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(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: ; 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 ≤ maxL, ; sprawdzamy, czy W jest tymczasowo najczęstsze
       to następny obieg pętli K2
K08:   maxL ← L ; jeśli tak, zapamiętujemy liczbę wystąpień
K09:   maxW ← W ; oraz wartość W
K10: Pisz maxW, maxL ; 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 <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ę 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
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ść

maxL = 0
for i in range(N):
    W, L = Z[i], 0
    for j in range(N):
        if Z[j] == W: L += 1
    if L > maxL:
        maxL, maxW = L, W

# Wypisujemy tablicę

for i in range(N):
    if Z[i] == maxW:
        print(" >%2d" % Z[i], end="")
    else:
        print("%4d" % Z[i], end="")

# Wypisujemy najczęstszy element oraz liczbę wystąpień

print()
print(maxW,":",maxL)
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

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ść 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 maxLmamy 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: maxW ← 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-maxL, ; zliczamy do n-maxL
     wykonuj kroki K05…K13
K05:   W ← Z[i] ; zapamiętujemy wartość bieżącego elementu
K06:   Jeśli W = maxW,     ; jeśli jest równa maxW,
       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 ≤ maxL,  ; zliczyliśmy więcej niż maxL?
       to idź do kroku K13
K11:   maxL ← L         ; jeśli tak, zapamiętujemy L w maxL
K12:   maxW ← W         ; oraz W w maxW
K13:   i ← i + 1 ; przechodzimy do kolejnego elementu Z[i]
K14: Pisz maxW, maxL    ; 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 <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ę 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
Python (dodatek)
# Najczęstsza wartość
# Data: 25.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 400 # Liczba elementów
Z = []  # Tablica

# Generujemy zawartość Z[]

for i in range(N):
    Z.append(random.randrange(100))

# Wyszukujemy najczęstszą wartość

maxL = 0
maxW = Z[0] - 1
i = 0
while i < N - maxL:
    W = Z[i];
    if maxW != W:
        L = 1;
        for j in range(i+1, N):
            if Z[j] == W: L += 1
        if L > maxL:
            maxL = L
            maxW = W
    i += 1
   
# Wypisujemy tablicę

for i in range(N):
    if Z[i] == maxW:
        print(" >%2d" % Z[i], end="")
    else:
        print("%4d" % Z[i], end="")
print()
print()

# Wypisujemy najczęstszy element oraz liczbę wystąpień

print(maxW, ":", maxL)
input()

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, 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: ; zliczamy wystąpienia wartości elementów
     wykonuj krok K04
K04: Zwiększ o 1 L[Z[i]-minZ ; w odpowiednich licznikach
K05: maxL ← L[0] ; szukamy max w L
K06: maxp ← 0
K07: Dla i = 1, 2, …, maxZ-minZ:
     wykonuj kroki K08…K10
K08:   Jeśli L[i] ≤ maxL,
       to następny obieg pętli K07
K09:   maxL ← L[i] ; zapamiętujemy wartość maksymalną
K10:   maxp ← i    ; oraz jej pozycję
K11: Pisz maxp+minZ, maxL ; 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

nL = maxZ-minZ+1
L = [0] * nL

# Zliczamy wystąpienia wartości z Z[]

for i in range(N):
    L[Z[i]- minZ] += 1

# Szukamy najczęstszej wartości w L[]

maxL,maxp = L[0],0
for i in range(nL):
  if L[i] > maxL:
    maxL,maxp = L[i],i

# Wyświetlamy wyniki

print()
print(maxp+minZ,":",maxL)
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

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

K01: maxL ← 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 ≤ maxL,      ; elementy nie są równe,
       to idź do kroku K08  ; sprawdzamy licznik L
K06:   maxL ← L ; jeśli L > maxL, to zapamiętujemy L
K07:   maxW ← 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 maxW, maxL ; 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
Z = []

# Inicjujemy tablicę Z[]

for i in range(N):
    Z.append(random.randrange(10))

# 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

maxL, L = 0, 1
for i in range(1, N+1):
    if Z[i] != Z[i-1]:
        if L > maxL:
            maxL, maxW = L, Z[i-1]
        L = 0
    L += 1

# Wyświetlamy wyniki

print(maxW,":",maxL)
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

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
©2024 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.