Matura - programowanie w C++

Algorytm wyszukiwania liniowego/sekwencyjnego

K01: Dla i =p, p+1,...,n-1:
     wykonuj K02  ; Przeglądamy kolejne elementy

K02:   Jeśli T[i] = w, ; Znalezione, pozycja
       to zakończ z wynikiem i

K03: Zakończ z wynikiem -1 ; Brak

W algorytmie powyższym sprawdzana jest równość T[i] = w. W rzeczywistości może to być dowolne kryterium (np. T[i] > w; T[i] < T[0]...). Wtedy otrzymamy ogólny algorytm wyszukiwania liniowego:

K01: Dla i =p, p+1,...,n-1:
     wykonuj K02

K02:   Jeśli kryterium spełnione,
       to zakończ z wynikiem i

K03: Zakończ z wynikiem -1

Poniższy program generuje tablicę 500-elementową i wypełnia ją liczbami pseudolosowymi o wartościach od 10 do 99. Następnie wyszukuje w niej wszystkie komórki zawierające liczbę 50 i zamienia ją na 1. Na koniec zawartość tablicy zostaje wyświetlona z zaznaczonymi komórkami o zawartości równej 1 – tutaj też stosowany jest podobny algorytm do wyszukiwania liniowego.

// Wyszukiwanie liniowe
//-------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Funkcja wyszukująca
//--------------------
int lsearch(int n, int T[], int p, int w)
{
    int i;

    for(i = p; i < n; i++)
        if(T[i] == w) return i;

    return - 1;
}

int main()
{
    int T[500],i,p;

    // tablicę wypełniamy liczbami pseudolosowymi

    srand(time(NULL));
    for(i = 0; i < 500; i++)
        T[i] = 10 + rand() % 90;

    // Szukamy wartości 50 i zamieniamy je na 1

    p = 0;
    while(p >= 0)
    {
        p = lsearch(500,T,p,50);
        if(p != -1) T[p++] = 1;
    }

    // Wyświetlamy wyniki

    for(i = 0; i < 500; i++)
        if(T[i] == 1) cout << "--1-";
        else cout << " " << T[i] << " ";

    cout << endl << endl;
    return 0;
}

 76  81  65  71  11  21  45  14  74  76  77  57  73  34  66  63  48  10  59  51
 70  57  94  51  66  72  31  15  29  21  97  33  23  17  83  11  95  66  21  66
 71  15  86  31  43 --1- 75  16  40  92  15  63  28  18  31  85  60  22  67  69
 65  84  73  39  21  95  58  72  86  68  77  53  25  77  69  75  24  38  81  25
 74  52  38  94  75  39  73  26  52  49  74  19  57  45  45  66  87  65  79  24
 98  15  62  52  57  97  79  19  11  95  68  73  86  44  94  87  92  46  47  30
 76  11  15  47  26  44 --1- 11  19 --1- 55  18  15  61  49  43  48  64  26  29
 34  49  47  35  65  47  72  69  63  53  75  85  30  53  25  42  99  23  71  19
 70  60  45  53  46  84  46  88  83  65  37  92  70  49  46  73  17  17  96  80
 24  80 --1- 62  36  97  38  63  88  19  25  52  84  91  42  75  43  45  94  55
 44  70  17  79  31  85  52  47  78  92  28  19  31  22  81  88  49  79  91  88
 29  38  53  61  51  58  75  77  92  58  97  61  63  47  55  27  49  15  96  81
 56  35  65  80  94  52  31  17  65  89  81  48  60  79  51  73  59  21  25  54
 23  63  68  48  86  43  18  77  26  78  37  97  77  31  48  57  71  38  85  44
 37  26  31  76  19  56  46  14  56  37  88  72  85  71  77  28  72  81  96  69
 77  32  64  33  95  94  55  23  36  42  85  88  20  60  77  94  11  29  10  69
 30  58  23  21  84  78  15  92  87  10  26  97  60  63  14  51  22  44  98  34
 92  91  94  66  36  61  43  17  33  63  41  57  83  46  79  27  70  81  21  55
 81  18  58  76  72  14  54  61  89  46  32  30  23  49  22  36  33  96  49  28
 85  28  62  40  14  96  25  59  12  41  63  81  28  15  15  83  54  60  90  39
 74  66  34  61  87  20  93  72  81  98  75  99  56  42  76  93  69  54  72  31
 14  35  67  37  98  75  19  98  66  10  77  36  93  76  36  52  58  94  12  53
 28  99  34  38  90  44  82  73  14  10  41  53  28  99  72  62  68  86  57  12
 32  98  87  11  11  22  93  94  70  84  72  94  17  27  64  64  59  52  45  22

Przeanalizuj dokładnie program, w szczególności fragment wykorzystujący wynik wyszukiwania.

Na podstawie powyższego programu napisz program, który:

1. Wyliczy ilość elementów o wartości większej od 80.
2. Obliczy sumę elementów o wartości mniejszej od 20.
3. Obliczy ilość elementów o wartości parzystej.
4. Dla twardzieli: Znajdzie i wypisze wszystkie pary elementów równych. Uwaga, jeśli w tablicy są trzy kolejne elementy równe, to tworzą dwie pary, np.:
   15,15,15 → (15, 15) i (15, 15).
   Podobnie cztery kolejne elementy równe, tworzą trzy pary; pięć, tworzy cztery pary; itd.

Przeanalizujmy algorytm wyszukiwania liniowego. W tym celu rozbijmy go na kroki równoważne:

K1: i ← p
K2: Jeśli i < n, idź do K4
K3: Zakończ z wynikiem -1
K4: Jeśli kryterium spełnione,
    to zakończ z wynikiem i
K5: i  ← i + 1
K6: Idź do K2

Policzmy czas wykonania. Oznaczmy czas wykonania kroku przez t_{numer kroku}. Załóżmy, iż w przeszukiwanym zbiorze żaden element nie spełnia kryterium wyszukiwawczego, to jest przypadek pesymistyczny. Wtedy pętla wykona się n-razy.

Czas wykonania będzie równy w przypadku pesymistycznym:

t = t1 + t3 + (n + 1) · t2 + n · (t4 + t5 + t6)

Przy dużych n możemy przyjąć, iż:

n + 1 ≈ n

Również czasy t₁ i t₃ możemy pominąć, gdyż są to czasy jednostkowe i przy dużych n nie wpływają istotnie na czas wykonania całości algorytmu. Otrzymamy zatem przybliżony wzór na czas wykonania algorytmu w przypadku pesymistycznym:

t ≈ n · (t2 + t4 + t5 + t6)

Dalsze uproszczenie będzie polegało na zastąpieniu czasów t₂, t₄, t₅ i t₆ czasem wykonania pętli t_p:

tp = t2 + t4 + t5 + t6
t ≈ n · tp

Zatem czas wykonania algorytmu jest proporcjonalny do n pomnożonego przez czas wykonania pętli. Jeśli uda nam się przyspieszyć wykonanie pętli, to algorytm ulegnie przyspieszeniu. Jak można przyspieszyć wykonanie pętli? Zwróć uwagę, iż pętla zawiera dwie instrukcje warunkowe, oznaczone tu kolorem czerwonym:

K1: i ← p
K2: Jeśli i < n,
    to idź do K4
K3: Zakończ z wynikiem -1
K4: Jeśli kryterium spełnione,
    to zakończ z wynikiem i
K5: i  ← i + 1
K6: Idź do K2

Instrukcja w kroku K2 jest wykonywana w celu sprawdzenia, czy indeks i nie wykroczył poza indeks ostatniego elementu tablicy. Jeśli poszukiwany element jest w przeszukiwanym zakresie, to algorytm dojdzie do jego indeksu i krok K4 zakończy wykonywanie algorytmu. Instrukcja warunkowa w kroku K2 nie będzie wykonana, jest zatem zbędna. Ale skąd mamy wiedzieć, czy poszukiwany element jest w zakresie poszukiwań? Zrobimy coś, co się może wydać szalone: sami wstawiamy poszukiwany element do tablicy, ale na jej końcu, poza jej elementami, czyli w komórce T[n] - wynika stąd, iż tablica musi posiadać o jedną komórkę więcej. Co nam to daje? Otóż dużo - przede wszystkim, jeśli pominiemy krok K2, to w przypadku braku poszukiwanego elementu w zakresie od T[0] do T[n - 1], algorytm znajdzie element dodany w komórce T[n]. Teraz wystarczy sprawdzić, czy indeks znalezionego elementu jest mniejszy od n. Jeśli tak, to jest to element rzeczywisty. Jeśli nie, to jest to element dodany, a zatem w zakresie podstawowym nie było poszukiwanego elementu. Dodany element nazywamy wartownikiem (ang. sentinel). Wartownik pilnuje, aby algorytm nie wyszedł poza zakres elementów tablicy. Dzięki niemu krok K2 staje się zbędny i pętla wykonywana jest szybciej. Zmodyfikowany algorytm wygląda następująco:

Algorytm wyszukiwania liniowego z wartownikiem

K01: T[n] ← w        ; ustawiamy wartownika
K02: i ← p           ; indeks elementu
K03: Jeśli T[n] = w,
     to idź do K06   ; sprawdzamy kryterium
K04: i  ← i + 1      ; następny indeks
K05: Idź do K3       ; powrót na początek pętli
K06  Jeśli i = n,    ; wartownik?
     to zakończ z -1 
K07: Zakończ z i     ; indeks elementu

Zwróć uwagę, iż algorytm jest dłuższy, jednak pętla K3, K4 i K5 zawiera tylko jedną instrukcję warunkową, a nie dwie jak poprzednio. Pozostałe instrukcje wykonują się tylko jeden raz, zatem nie wpływają istotnie na czas wykonania algorytmu.

Algorytm wyszukiwania liniowego w przypadku pesymistycznym ma klasę złożoności obliczeniowej O(n), czyli liniową. Wyszukiwanie z wartownikiem jest szybsze od zwykłego wyszukiwania, chociaż algorytm jest nieco bardziej skomplikowany.

 W poprzednim programie zamień funkcję lsearch( ) na:

...

// Funkcja wyszukująca
//--------------------
int lsearch(int n, int T[], int p, int w)
{
    int i;
    T[n] = w; // wartownik
    for(i = p; T[i] != w; i++);
    if(i == n) return -1;
    else       return i;
    return - 1;
}

...

Rozmiar tablicy ustaw na T[501].

Do zapamiętania:

• Co to jest wartownik w algorytmie wyszukiwania?
• Dlaczego wyszukiwanie z wartownikiem jest szybsze od zwykłego wyszukiwania?

Algorytm wyszukiwania elementu największego (najmniejszego)

K01: w ← T[0]     ; wartość zapamiętana
K02: p ← 0        ; pozycja wartości zapamiętanej
K03: Dla i = 1,2,...,n-1:
     wykonuj K04  ; przeglądamy pozostałe elementy
K04:   Jeśli T[i] > (<) w, to
          w ← T[i]; zapamiętujemy element większy (mniejszy) od w
          p ← i   ; do w trafia wartość elementu
                  ; do p trafia pozycja (indeks) elementu
K05: Zakończ      ; wynik w w i p

Poniższy program tworzy tablicę 100 elementową i wypełnia ją liczbami pseudolosowymi od 10 do 99. Następnie wyszukuje w niej element największy.

// Wyszukiwanie elementu max
//--------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Funkcja wyszukująca
int maxsearch(int n, int T[], int & p)
{
    int w = T[0];
    p = 0;
    for(int i = 1; i < n; i++)
        if(T[i] > w)
        {
            w = T[i];
            p = i;
        }
    return w;
}

int main()
{
    int T[100],i,p,v;

    // Wypełniamy tablicę
    srand(time(NULL));
    for(i = 0; i < 100; i++)
        T[i] = 10 + rand() % 90;

    // Szukamy wartości max
    v = maxsearch(100,T,p);

    // Wyniki
    cout << "MAX = " << v
         << " na pozycji << " << p
         << "." << endl << endl;
    for(i = 0; i < 100; i++)
        if(i == p) cout << "(" << T[i] << ")";
        else       cout << " " << T[i] << " ";
    cout << endl << endl;
    return 0;
}

 MAX = 98 na pozycji << 18.

 40  19  30  50  20  17  71  81  54  41  58  82  97  91  55  71  13  58 (98) 39
 52  84  20  30  88  53  29  87  10  42  67  53  36  59  35  88  45  75  66  35
 79  80  81  96  74  20  51  86  55  30  24  77  42  46  59  20  66  55  59  68
 52  87  29  33  39  84  65  36  78  45  98  37  86  81  70  69  76  95  14  27
 34  38  41  52  96  10  96  11  32  46  81  48  26  43  20  63  15  20  33  23 

Przerób program tak, aby wyszukiwał element minimalny.

Do zapamiętania:

• Algorytm wyszukiwania elementu największego/najmniejszego

Algorytm nr 1 wyszukiwania MIN i MAX

K01: wmin ← T[0] ; wartość minimalna
K02: pmin ← 0    ; i jej pozycja
K03: wmax ← T[0] ; wartość maksymalna
K04: pmax ← 0    ;  o jej pozycja
K05: Dla i = 1,2,...,n-1: ; przeglądamy pozostałe elementy
     wykonuj kroki K06...K7
K06: Jeśli T[i] > wmax, to
        wmax ← T[i] ; wartość większa
        pmax ← i    ; i jej pozycja
K07: Jeśli T[i] < wmin, to
        wmin ← T[i] ; wartość mniejsza
        pmin ← i    ; i jej pozycja
K08: Zakończ ; wynik w wmax, pmax, wmin, pmin

W przykładowym programie tworzona jest tablica 15 elementowa, która zostaje wypełniona liczbami pseudolosowymi rzeczywistymi od -2 do 2. Następnie program wyszukuje wartość MIN i MAX.

// Wyszukiwanie MIN i MAX - 1
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

// Funkcja wyszukująca
void mmsearch(int n, double T[],
              double & wmin, int & pmin,
              double & wmax, int & pmax)
{
    wmax = wmin = T[0];
    pmax = pmin = 0;

    for(int i = 0; i < n; i++)
    {
        if(T[i] > wmax)
        {
            wmax = T[i];
            pmax = i;
        }
        if(T[i] < wmin)
        {
            wmin = T[i];
            pmin = i;
        }
    }
}

int main()
{
    double T[15],w1,w2;
    int i,p1,p2;

    cout << fixed << setprecision(4);

    // generujemy liczby w T[]

    srand(time(NULL));
    for(i = 0; i < 15; i++)
        T[i] = -2 + (rand() / (double) RAND_MAX) * 4;

    // szukamy MIN i MAX

    mmsearch(15,T,w1,p1,w2,p2);

    // wyniki

    cout << "MIN = " << setw(7) << w1
         << " na pozycji " << setw(2) << p1 << endl
         << "MAX = " << setw(7) << w2
         << " na pozycji " << setw(2) << p2 << endl << endl;
    for(i = 0; i < 15; i++)
    {
        cout << setw(2) << i << " : "
             << setw(7) << T[i];
        if(i == p1) cout << " : MIN";
        if(i == p2) cout << " : MAX";
        cout << endl;
    }
    cout << endl << endl;

    return 0;
}

MIN = -1.8702 na pozycji 11
MAX =  1.9377 na pozycji 10

 0 :  1.6576
 1 : -0.0336
 2 : -0.5876
 3 : -1.3581
 4 :  0.1942
 5 : -0.0142
 6 : -1.2439
 7 : -0.4619
 8 :  1.3254
 9 : -0.6723
10 :  1.9377 : MAX
11 : -1.8702 : MIN
12 :  1.8680
13 : -1.4326
14 :  0.1546

Przeanalizujmy teraz zaprezentowany wyżej algorytm. W pętli przeglądającej tablicę są dwie operacje porównań:

K01:

wmin ← T[0]

K02:

pmin ← 0

K03:

wmax ← T[0]

K04:

pmax ← 0

K05:

Dla i = 1,2,...,n-1: wykonuj K06...K7

K06:

    Jeśli T[i] > wmax, to
        wmax ← T[i]
        pmax ← i

K07:

    Jeśli T[i] < wmin, to
        wmin ← T[i]
        pmin ← i

K05:

Zakończ

Pętla przegląda tablicę od elementu o indeksie 1 do ostatniego, zatem jeśli tablica ma n-elementów, to pętla wykona się n - 1 razy. W każdym obiegu mamy 2 operacje porównań, zatem liczba wszystkich porównań dla całej tablicy wyniesie:

2 · (n - 1) = 2n - 2

Jeśli uda się nam zmniejszyć liczbę porównań, to przyspieszymy algorytm.

Wyobraźmy sobie, iż liczba elementów tablicy jest parzysta – jeśli nie jest parzysta, to na końcu dublujemy ostatni element. Podzielmy teraz wszystkie elementy na pary: pierwszy z drugim, trzeci z czwartym, piąty z szóstym, itd. Par będzie dwa razy mniej niż tworzących je elementów, czyli n / 2. Bierzemy parę i porównujemy ze sobą zawarte w niej elementy:

Co nam to dało? Porównań elementów w parach jest tyle, ile jest par, zatem n / 2. Porównanie takie rozdziela parę na element a i element b. Każdy z tych elementów jest następnie porównywany z MIN lub z MAX. Porównań tych jest po n / 2. Zatem sumarycznie mamy porównań:

n/2 + n/2 + n/2 = 3/2 n
1,5n < 2n - 2

Zmniejszyliśmy ilość porównań mniej więcej o 1/4, a zatem tak skonstruowany algorytm będzie szybszy. Zapiszmy go:

Algorytm nr 2 wyszukiwania MIN i MAX

K01: Jeśli n nieparzyste, ; Jeśli nieparzysta liczba elementów,
     to T[n] ← T[n-1]     ; to dublujemy ostatni element
K02: wmin ← największa liczba
K03: wmax ← najmniejsza liczba
K04: i ← 0
K05: Dopóki i < n,        ; Wybieramy pary elementów
     wykonuj kroki K06...K12
K06:   Jeśli T[i] > T[i+1],
       to idź do K10     ; rozdzielamy je na element mniejszy i większy
K07:   Jeśli T[i] < wmin, to   ; T[i] porównujemy z wmin
         wmin ← T[i]
         pmin ← i
K08:   Jeśli T[i+1] > wmax, to ; T[i+1] porównujemy z wmax
         wmax ← T[i+1]
         pmax ← i+1
K09:   Idź do K12
K10:   Jeśli T[i+1] < wmin, to ; T[i+1] porównujemy z wmin
         wmin ← T[i+1]
         pmin ← i+1
K11:   Jeśli T[i] > wmax, to   ; T[i] porównujemy z wmax
         wmax ← T[i]
         pmax ← i
K12:   i ← i + 2 ; Następna para
K13: Zakończ

Poniżej mamy poprzedni program ze zmodyfikowanym algorytmem wyszukiwania MIN i MAX:

// Wyszukiwanie MIN i MAX - 2
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

// Funkcja wyszukująca
void mmsearch(int n, double T[],
              double & wmin, int & pmin,
              double & wmax, int & pmax)
{
    if(n % 2) T[n] = T[n-1];

    wmax = 2.2250738585072014e-308;
    wmin = 1.7976931348623158e+308;

    for(int i = 0; i < n; i+= 2)
    {
        if(T[i] > T[i+1])
        {
            if(T[i+1] < wmin)
            {
                wmin = T[i+1];
                pmin = i + 1;
            }
            if(T[i] > wmax)
            {
                wmax = T[i];
                pmax = i;
            }
        }
        else
        {
            if(T[i] < wmin)
            {
                wmin = T[i];
                pmin = i;
            }
            if(T[i+1] > wmax)
            {
                wmax = T[i+1];
                pmax = i+1;
            }
        }
    }
}

int main()
{
    double T[15],w1,w2;
    int i,p1,p2;

    cout << fixed << setprecision(4);

    // generujemy liczby w T[]

    srand(time(NULL));
    for(i = 0; i < 15; i++)
        T[i] = -2 + (rand() / (double) RAND_MAX) * 4;

    // szukamy MIN i MAX

    mmsearch(15,T,w1,p1,w2,p2);

    // wyniki

    cout << "MIN = " << setw(7) << w1
         << " na pozycji " << setw(2) << p1 << endl
         << "MAX = " << setw(7) << w2
         << " na pozycji " << setw(2) << p2 << endl << endl;
    for(i = 0; i < 15; i++)
    {
        cout << setw(2) << i << " : "
             << setw(7) << T[i];
        if(i == p1) cout << " : MIN";
        if(i == p2) cout << " : MAX";
        cout << endl;
    }
    cout << endl << endl;

    return 0;
}

MIN = -1.8596 na pozycji  7
MAX =  1.8347 na pozycji 11

 0 : -1.0263
 1 :  1.6163
 2 :  1.0276
 3 :  0.0247
 4 : -0.4040
 5 :  0.4260
 6 :  1.6075
 7 : -1.8596 : MIN
 8 :  1.0334
 9 : -1.2943
10 :  1.1568
11 :  1.8347 : MAX
12 : -1.5991
13 : -1.1771
14 : -0.5654

Podany algorytm wykorzystuje zasadę dziel i zwyciężaj (ang. divide and conquer). Polega ona na podzieleniu problemu na problemy mniejsze, rozwiązaniu problemów mniejszych i z tych rozwiązań stworzenia rozwiązania problemu głównego.

Do zapamiętania:

• Algorytm 2 jednoczesnego wyszukiwania MIN i MAX.

Naszym zadaniem jest znalezienie w zbiorze wartości, która powtarza się najczęściej. Na przykład mamy zbiór:

{ 5 4 8 9 4 5 3 5 2 1 }

Wartość 5 powtarza się 3 razy i jest wartością najczęstszą.

Problem można rozwiązać na wiele sposobów. Zacznijmy od najprostszego.

Algorytm wyszukiwania najczęstszej wartości - wersja 1

K01: maxc ← 0 ; zerujemy maksymalną liczbę powtórzeń
K02: Dla i = 0,1,2,...,n-1: ; przeglądamy kolejne elementy tablicy
     wykonuj K03...K07
K03:   w ← T[i] ; zapamiętujemy wartość
K04:   c ← 0    ; zerujemy licznik wystąpień
K05:   Dla j = 0,1,2,...,n-1:
       wykonuj krok K06
K06:     Jeśli T[j] = w, ; zliczamy wystąpienia wartości w
         to c ← c + 1
K07    Jeśli c > maxc, ; jeśli liczba wystąpień jest większa od
       to maxc ← c     ; maksymalnej, to uaktualniamy maxc
          maxw ← w     ; i maxw
K08: Zakończ ; wyniki w maxc i maxw

Poniższy program tworzy tablicę 100 elementową i wypełnia ją liczbami pseudolosowymi od 1 do 25. Następnie wyszukuje element, który powtarza się najczęściej. Przeanalizuj dokładnie program.

// Wyszukiwanie najczęstszej wartości - 1
//---------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    // inicjujemy generator pseudolosowy

    srand(time(NULL));

    // Tworzymy tablicę i wypełniamy ją

    int i,T[100];

    for(i = 0; i < 100; i++) T[i] = 1 + rand() % 25;

    // Wyszukujemy najczęstszy element

    int c,w,maxc,maxw,j;

    maxc = 0;
    for(i = 0; i < 100; i ++)
    {
        w = T[i];
        c = 0;
        for(j = 0; j < 100; j++) if(T[j] == w) c++;
        if(c > maxc)
        {
            maxc = c;
            maxw = w;
        }
    }

    // Wyniki

    for(i = 0; i < 100; i++)
    {
        if(T[i] == maxw) cout << "->";
        else             cout << "  ";
        cout << setw(2) << T[i];
    }
    cout << endl << maxw << " x " << maxc
         << endl << endl;

    return 0;
}

->21  17   5   1  10   7   6   1  25  11  22  12   8  23   1  11   5  16   5  13
  23  12  24  18  10  10   1   8  19  24  11  22   1  22  24  23   4  14  20   8
  20  12   6  24->21  22   8  24  14   5  18   5  20  20  23   1->21  22  25->21
  18   4  12   9  24  10   3   3   8->21  20->21  17   3  18  24  19  12   6   3
  12  11  10  20   5   2   3   8  25   3   3   7->21   9   7  11  18  18   6  23

21 x 7

Pierwszy algorytm jest prosty, lecz bardzo prymitywny i wykonuje wiele niepotrzebnych operacji. Co możemy poprawić?

1. Z tablicy bierzemy KAŻDY element T[i] i zliczamy wystąpienia jego wartości  w CAŁEJ tablicy T[ ]. W ten sposób najczęstsza wartość maxw zostanie zliczona maxw² razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element w tablicy 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 T[0] (dlaczego?).
2. Każdy element T[i] zliczamy w całej tablicy. Tymczasem, jeśli wartość i-tego elementu wystąpiła wcześniej w tablicy, 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 tablicy. 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 maxc mamy chwilową maksymalną liczbę wystąpień pewnej wartości maxw, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n - maxc. Jeśli nowy element występuje na tej lub dalszej pozycji w tablicy T[ ], to liczba wystąpień jego wartości nie będzie już większa od maxc, gdyż braknie elementów.

Po tych modyfikacjach otrzymujemy:

Algorytm wyszukiwania najczęstszej wartości - wersja 2

K01: maxc ← 0          ; licznik wystąpień
K02: maxw ← T[0] - 1   ; najczęstsza wartość musi być różna od T[0]
K03: Dla i = 0,1,2,...,n-maxc-1:
     wykonuj K04...K09 ; zliczamy powtórzenia elementów
K04:   w ← T[i]        ; zapamiętujemy wartość elementu
K05:   Jeśli w = maxw, ; pomijamy element T[i], jeśli równy maxw
       to następny obieg
K06:   c ←1            ; T[i] już raz zliczony
K07:   Dla j = i+1,i+2,...,n-1:
       wykonuj K08     ; zliczanie od następnych elementów
K08:     Jeśli T[j] = w, to c ← c + 1
K09:   Jeśli c > maxc, ; Jeśli zliczyliśmy więcej od maxc, to uaktualniamy
       to maxc ← c     ; maxc - liczba wystąpień
          maxw ← w     ; maxw - powtarzająca się wartość
K10: Zakończ           ; wynik w maxc i maxw

Uaktualniony program

/// Wyszukiwanie najczęstszej wartości - 2
//---------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    // inicjujemy generator pseudolosowy

    srand(time(NULL));

    // Tworzymy tablicę i wypełniamy ją

    int i,T[100];

    for(i = 0; i < 100; i++) T[i] = 1 + rand() % 25;

    // Wyszukujemy najczęstszy element

    int c,w,maxc,maxw,j;

    maxc = 0;
    maxw = T[0] - 1;
    for(i = 0; i < 100 - maxc; i ++)
    {
        w = T[i];
        if(w == maxw) continue;
        c = 1;
        for(j = i + 1; j < 100; j++) if(T[j] == w) c++;
        if(c > maxc)
        {
            maxc = c;
            maxw = w;
        }
    }

    // Wyniki

    for(i = 0; i < 100; i++)
    {
        if(T[i] == maxw) cout << "->";
        else             cout << "  ";
        cout << setw(2) << T[i];
    }
    cout << endl << maxw << " x " << maxc
         << endl << endl;

    return 0;
}

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 T[ ]. Zakres indeksów w L[ ] możemy znaleźć wyszukując w tablicy T[ ] 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 T[ ]). Zerujemy wszystkie liczniki w L[ ] i przeglądamy tablicę T[ ] 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 T[ ] 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 T[ ] oraz zawartość elementu L[ ] o tym indeksie, która określa ile razy dana wartość wystąpiła w T[ ].

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.

W języku C++ indeksy tablicy rozpoczynają się od wartości 0. Jeśli indeksy mają odpowiadać wartościom elementów tablicy, to wartości te należy odpowiednio przeliczyć. Na przykład mamy przedział wartości <-2, 3>. W przedziale tym są liczby:

-2 -1 0 1 2 3

Jeśli mamy zliczać wystąpienia tych wartości, to musimy przygotować tablicę liczników tak, aby ich indeksy odpowiadały zliczanym wartościom:

Jeśli mamy przedział całkowity <a,b>, to w przedziale tym jest b - a + 1 różnych wartości. Wyrażenie to pozwoli wyliczyć rozmiar tablicy liczników, jeśli znamy zakres wartości. Zakres a...b poznamy wyznaczając MIN i MAX liczb w przeszukiwanej tablicy. Wzory przeliczeniowe pomiędzy indeksami liczników, a zliczanymi przez nie wartościami są następujące:

indeks = wartość - MIN
wartość = indeks + MIN

Zatem pełny algorytm wygląda następująco:

Algorytm wyszukiwania najczęstszej wartości - wersja 3

K01: Wyznacz minwt i maxtw w T[ ] ; szukamy MIN i MAX w T[ ]
K02: Utwórz dynamicznie tablicę L[ ]
     o maxtw - mintw + 1 komórkach
K03: Wyzeruj komórki tablicy L[ ] ; zerujemy liczniki
K04: Dla i = 0,1,2,...,n-1:
     wykonuj krok K05             ; przeglądamy tablicę T[ ]
K05:   Zwiększ o 1 licznik
       L[T[i] - mintw]            ; zliczamy napotkaną wartość
K06: Wyznacz maxlw i maxlp w L[ ] ; szukamy największego licznika i jego pozycji
K07  maxw ← maxlp + mintw         ; najczęstsza wartość
K08: maxc ← maxlw                 ; liczba powtórzeń
K09: Usuń tablicę dynamiczną L[ ]
K10: Zakończ

Zmodyfikowany program:

// Wyszukiwanie najczęstszej wartości - 3
//---------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    // inicjujemy generator pseudolosowy

    srand(time(NULL));

    // Tworzymy tablicę i wypełniamy ją

    const int N = 100;
    int i,T[N];

    for(i = 0; i < N; i++) T[i] = 1 + rand() % 25;

    // znajdujemy MIN i MAX w T[ ]

    int mintw,maxtw,m;

    mintw = maxtw = T[0];
    for(i = 1; i < N; i++)
    {
        if(T[i] < mintw) mintw = T[i];
        if(T[i] > maxtw) maxtw = T[i];
    }

    // Tworzymy tablicę liczników L[ ]

    m = maxtw - mintw + 1; // Rozmiar
    int * L = new int[m];

    // Zerujemy liczniki

    for(i = 0; i < m; i++) L[i] = 0;

    // Zliczamy wartości z T[ ]

    for(i = 0; i < N; i++) L[T[i] - mintw]++;

    // Szukamy największego licznika i jego indeksu

    int maxlw,maxlp;

    maxlw = L[0];
    maxlp = 0;

    for(i = 1; i < m; i++)
        if(L[i]>maxlw)
        {
            maxlw = L[i];
            maxlp = i;
        }

    // Przeliczamy

    int maxw = maxlp + mintw;
    int maxc = maxlw;

    // Wyniki

    for(i = 0; i < 100; i++)
    {
        if(T[i] == maxw) cout << "->";
        else             cout << "  ";
        cout << setw(2) << T[i];
    }
    cout << endl << maxw << " x " << maxc
         << endl << endl;

    delete [] L;

    return 0;
}

Taki algorytm jest efektywny tylko wtedy, gdy zbiór danych posiada ograniczoną liczbę wartości, lecz sam jest duży. Na maturze raczej takich problemów nie zadaje się uczniom z uwagi na ograniczony czas trwania egzaminu. Dlatego algorytm nr 2 powinien być wystarczający.

Do zapamiętania:

• Algorytmy 1 i 2 (3 dla chętnych).

Zbiór uporządkowany możemy utworzyć w prosty sposób przy pomocy liczb pseudolosowych:

Poniższy program tworzy cztery zbiory o różnych porządkach.

// Zbiory uporządkowane
//---------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,""); // Polskie znaki

    srand(time(NULL)); // Inicjalizacja LCG

    int w,i;

    cout << "Porządek rosnący     : ";
    w = rand() % 10;
    for(i = 0; i < 14; i++)
    {
        cout << setw(4) << w;
        w += 1 + rand() % 30;
    }
    cout << endl << endl;
    //-------------------------------
    cout << "Porządek malejący    : ";
    w = 20 + rand() % 20;
    for(i = 0; i < 14; i++)
    {
        cout << setw(4) << w;
        w -= 1 + rand() % 10;
    }
    cout << endl << endl;
    //-------------------------------
    cout << "Porządek niemalejący : ";
    w = 25 + rand() % 10;
    for(i = 0; i < 14; i++)
    {
        cout << setw(4) << w;
        w += rand() % 5;
    }
    cout << endl << endl;
    //-------------------------------
    cout << "Porządek nierosnący  : ";
    w = 10 + rand() % 10;
    for(i = 0; i < 14; i++)
    {
        cout << setw(4) << w;
        w -= rand() % 5;
    }
    cout << endl << endl;
    return 0;
}

Porządek rosnący     :   9  12  22  43  63  77  81  84 106 109 126 144 149 150

Porządek malejący    :  36  27  17  10   3  -1  -8 -18 -25 -29 -30 -35 -36 -37

Porządek niemalejący :  31  31  35  39  40  40  43  43  46  47  51  54  58  61

Porządek nierosnący  :  13   9   7   5   2  -2  -6  -6  -8 -10 -12 -13 -15 -17

Do zapamiętania:

• Zbiór uporządkowany.
• Porządek mocny i słaby.
• Porządek: rosnący, malejący, niemalejący, nierosnący.

Wyszukiwanie binarne (ang. binary search) odnosi się do zbiorów uporządkowanych, ponieważ korzysta ono z porządku w zbiorze. Postępujemy następująco:

Ponieważ w każdym obiegu pętli algorytm redukuje liczbę elementów o połowę, to jego klasa złożoności obliczeniowej jest równa O(log n). Jest to bardzo korzystna złożoność. Na przykład w algorytmie wyszukiwania liniowego przy 1000000 elementów należało wykonać aż 1000000 porównań, aby stwierdzić, iż elementu poszukiwanego nie ma w zbiorze. W naszym algorytmie wystarczy tylko 20 porównań.

Algorytm wyszukiwania liniowego może być zastosowany dla dowolnego zbioru. Algorytm wyszukiwania binarnego można stosować tylko i wyłącznie w zbiorze uporządkowanym.

Musimy uściślić sposób podziału zbioru na coraz mniejsze fragmenty. Zbiór odwzorowujemy w tablicy T[ ]  składającej się z n  elementów ponumerowanych kolejno od 0 do n - 1. Określmy dwa indeksy:

i_p  – indeks pierwszego elementu zbioru
i_k  – indeks końcowego elementu zbioru

Indeksy i_p  i i_k  określają obszar zbioru w tablicy T[  ]. Początkowo będą oczywiście równe: i_p  = 0 oraz i_k  = n  - 1. Na podstawie tych dwóch indeksów obliczamy indeks elementu środkowego i_sr:

Jeśli zbiór  jest uporządkowany rosnąco, to:

Zatem w przypadku, gdy poszukiwana wartość w  < T[i_sr], to przechodzimy do pierwszej połówki, w której indeksy przebiegają od i_p do i_sr-1. Element T[i_sr] pomijamy, gdyż wiadomo, że o niego nam nie chodzi.

Jeśli w  > T[i_sr], to przechodzimy do drugiej połówki o indeksach od i_sr + 1 do i_k.

Jeśli w wyniku redukcji indeks i_p stanie się większy od i_k, to wyszukiwanie kończymy, ponieważ taka połówka nie zawiera żadnego elementu, zatem poszukiwanego elementu w zbiorze nie ma.

W przypadku porządku słabego tablica może posiadać wielkości równe w kilku kolejnych komórkach. W takim przypadku algorytm wyszukiwania binarnego wskaże jedną z nich.

Algorytm wyszukiwania binarnego

K01: p ← -1 ; zakładamy, iż w nie występuje w tablicy
K02: ip ← 0; ik ← n - 1 ; indeksy początku i końca
K03: Dopóki ip ≤ ik:    ; w pętli poszukujemy elementu o wartości w
     wykonuj kroki K04...K11
K04:   isr = (ip + ik) / 2 ; wyznaczamy element środkowy, dzielenie całkowite
K05:   Jeśli w ≠ T[isr],
       to idź do kroku K08
K06:   p  ← isr        ; element znaleziony, kończymy
K07:   Zakończ pętlę
K08:   Jeśli w < T[isr],
       to idź do K11   ; wybieramy odpowiednią połówkę zbioru
K09:   ip ← isr + 1    ; w > T[isr] → druga połówka
K10:   Następny obieg pętli
K11:   ik  ← isr - 1   ; w < T[isr] → pierwsza połówka
K12: Zakończ z wynikiem p

Poniższy program tworzy tablicę 208 elementową i umieszcza w niej wartości uporządkowane w kolejności rosnącej. Następnie wybiera jedną z tych wartości i dodaje liczbę pseudolosową 0 lub 1, po czym tak zmodyfikowaną wartość wyszukuje w tablicy.

// Wyszukiwanie binarne
//---------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,""); // Polskie znaki

    srand(time(NULL)); // Inicjalizacja LCG

    // Tworzymy tablicę z porządkiem rosnącym
    const int N = 208;
    int T[N],i;
    T[0] = rand() % 10;
    for(i = 1; i < N; i++)
    {
         T[i] = T[i - 1] + 1 + rand() % 3;
    }

    // Szukamy wartości w

    int w,p,ip,ik,isr;

    w = T[rand() % N] + rand() % 2;
    p = -1;
    ip = 0; ik = N - 1;
    while(ip <= ik)
    {
        isr=(ip+ik) / 2;
        if(T[isr] == w)
        {
            p = isr;
            break;
        }
        if(w > T[isr]) ip = isr + 1;
        else           ik = isr - 1;
    }

    // Wyniki

    for(i = 0; i < N; i++)
    {
        if(i == p) cout << "->";
        else       cout << "  ";
        cout << setw(3) << T[i];
    }
    cout << endl;
    if(p >= 0)
        cout << "Wartość " << w << " na pozycji " << p;
    else
        cout << "W tablicy brak " << w;
    cout << endl << endl;

    return 0;
}

    4    7    8    9   10   13   15   16   18   21   23   26   28   30   32   33
   36   37   40   42   45   47   48   50   52   53   56   57   60   61   62   64
   66   68   69   70   71   74   75   76   79   82   85   88   89   92   95   98
  101  104  106  109  111  112  113  115  116  119  122  123  125  128  131  134
  137  138  139  140  142  143  146  149  152  154  156  158  161  164  165  168
  170  172  175  177  179  180  182  184  185  188  189  191  194  195  196  197
  199  202  203  204  206  208  209  211  212  215  218  219  220  223  224  225
  227  228  229  230  232  234  237  240  243  245  248  250  251  252  253  254
  257  260  262  265  266  269  272  274  277  280  281  284  287  290  292  295
  296  297  300  303  306  307  310  313  314  316  319  320  322  323  325  326
  328  331  333  336  338  339  342  344  347  349  352  354  357  358  361  364
  367  370  372  373  376  379  382  385  388  391  393  396  398  400  403  405
  406  407  410  412  414  417  420  422  424  425  427  428->429  431  434  436

Wartość 429 na pozycji 204

Do zapamiętania:

• Algorytm wyszukiwania binarnego.

Lider (ang. leader) jest wartością występującą w ponad połowie elementów zbioru. Na przykład w zbiorze:

{ 1 4 7 4 3 4 4 8 4 4 }

liderem jest wartość 4, ponieważ pojawia się w zbiorze 6 razy, a zbiór liczy 10 elementów, czyli 4 występuje w więcej niż w połowie elementów.

Lidera można znaleźć przedstawionym wcześniej algorytmem wyszukiwania najczęstszej wartości (jak to zrobić?). Jednakże istnieje prostszy i szybszy sposób. Wykorzystujemy tu twierdzenie:

Jeśli tablica T[ ] posiada lidera, to usunięcie z niego pary elementów różnych daje zbiór z tym samym liderem.

Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez n_L liczbę elementów będących liderami. Tablica T[ ]  posiada n elementów, zatem liczba pozostałych elementów wynosi n - n_L. Zachodzi nierówność:

nL > n - nL

Przypadek 1

Z tablicy T[ ] usuwamy dwa elementy, które nie są liderami. W tym przypadku n_L nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:

nL > (n - 2) - nL
nL > (n - nL) - 2

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż n_L  jest liczebnością liderów ), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.

Przypadek 2

Z tablicy T[ ] usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:

nL - 1 > (n - 2) - (nL - 1)
nL - 1 > n - 2 - n L  + 1
nL - 1 > (n - nL) - 1
nL > n - nL

Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie z tablicy T[ ] jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.

Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.

Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:

Zamiast faktycznie wyrzucać z tablicy elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:

Licznik elementów równych L  stawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L o 1. W przeciwnym razie licznik L  zmniejszamy o 1 – odpowiada to wyrzuceniu z tablicy dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli tablica posiadała lidera, to liczba elementów równych jest większa od liczby elementów różnych. W takim przypadku zapamiętana wartość jest liderem. Aby to potwierdzić, zliczamy liczbę wystąpień tej wartości w tablicy. Jeśli jest ona większa od liczby połowy elementów, to mamy lidera.

Algorytm posiada liniową klasę złożoności obliczeniowej O(n), jest zatem bardziej efektywny od opisanych w wcześniej algorytmów wyszukiwania najczęstszej wartości.

Algorytm wyszukiwania lidera w zbiorze

K01: L ← 0              ; licznik wartości równych
K02: Dla i = 0,1,...,n-1: ; przeglądamy kolejne elementy
     wykonuj K03...K07
K03:   Jeśli L > 0,     ; sprawdzamy, czy licznik równy 0
       to idź do kroku K07
K04:   w ← T[i ]        ; jeśli tak, zapamiętujemy bieżący element
K05:   L ← 1            ; zaliczamy ten element
K06:   Następny obieg pętli K02
K07:   Jeśli w = T[i ], ; elementy równe zliczamy, elementy różne wyrzucamy
       to L ← L + 1
       inaczej L ← L - 1
K08: Jeśli L = 0,       ; sprawdzamy, czy w jest kandydatem na lidera
     to idź do kroku K13
K09: L ← 0              ; jeśli tak, to sprawdzamy, czy w jest faktycznie liderem
K10: Dla i = 0,1,...,n-1: ; zliczamy jego wystąpienia w tablicy
     wykonuj krok K11
K11:   Jeśli T[i] = w,
       to L ← L + 1
K12: Jeśli L > [n:2],   ; lider?
     to idź do kroku K14
K13: L = -1             ; ujemna liczba wystąpień to brak lidera
K14: Zakończ z w, L

Poniższy program tworzy tablicę o 200 elementach i wypełnia ją liczbami pseudolosowymi od 0 do 99 w taki sposób, aby zaistniała szansa pojawienia się lidera. Następnie lider jest wyszukiwany naszym algorytmem.

// Wyszukiwanie lidera
//--------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,""); // Polskie znaki

    srand(time(NULL)); // Inicjalizacja LCG

    // Tworzymy tablicę z potencjalnym liderem

    const int N = 200; // Liczebność zbioru

    int w,i,T[N];

    w = rand() % 100; // Lider 0...99

    for(i = 0; i < N; i++)
        if(rand() % 2) T[i] = w;
        else           T[i] = rand() % 100;

    // Szukamy lidera

    int L;
    L = 0;
    for(i = 0; i < N; i++)
        if(!L)
        {
            w = T[i];
            L = 1;
        }
        else if(w == T[i]) L++;
             else          L--;
    if(L)
    {
        L = 0;
        for(i = 0; i < N; i++)
            if(T[i] == w) L++;
        if(L <= N / 2) L = -1;
    }
    else L = -1;

    // Wyniki

    for(i = 0; i < N; i++)
    {
        if((L > 0) && (T[i] == w)) cout << " >";
        else                       cout << "  ";
        cout << setw(2) << T[i];
    }
    cout << endl;
    if(L > 0) cout << "lider = " << w << " x " << L;
    else      cout << "Brak lidera";
    cout << endl << endl;

    return 0;
}

  55 >16  37  60   4 >16  18  31   8  14 >16  36  62  62 >16 >16  99  25  52  63
 >16 >16  78  39  59 >16  62 >16 >16 >16 >16 >16  83  27 >16  37  27  40  65 >16
 >16  48  11  53  64 >16 >16 >16  55 >16  50 >16 >16   3 >16  91  93  98 >16  76
 >16 >16 >16  78 >16  61  98  38   6  26 >16 >16  38 >16 >16 >16  18 >16   5 >16
 >16 >16  11 >16 >16 >16   1 >16 >16  78  94 >16 >16 >16 >16   9 >16  90 >16  12
 >16  91 >16 >16  55  64 >16 >16 >16 >16  88 >16 >16 >16 >16  79 >16 >16  26  11
 >16   9 >16  98 >16  43  63 >16  84  89 >16  32 >16 >16  72 >16  98 >16  10 >16
 >16 >16  78  21   7 >16 >16  53  15  22 >16  60   4   4 >16  49 >16  98 >16  92
 >16 >16   8 >16 >16  83  90  45  17 >16 >16 >16  55  19 >16  34 >16  52 >16   6
 >16 >16  95  12  56 >16  75  27 >16 >16 >16  25 >16 >16 >16  72  31 >16 >16 >16

lider = 16 x 101

Do zapamiętania:

• Definicja lidera.
• Algorytm wyszukiwania lidera.