Algorytmy i Struktury Danych - Wyszukiwanie lidera

Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru \(Z\). Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.

Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:

Jeśli zbiór \(Z\) 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. Zbiór \(Z\) posiada n elementów, zatem liczba pozostałych elementów wynosi \({n - n_L}\). Zachodzi nierówność:

n_L> n-n_L

Przypadek 1

Ze zbioru \(Z\) 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:

n_L > (n-2)-n_L
n_L > (n-n_L)-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

Ze zbioru \(Z\) 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:

n_L-1 > (n-2)-(n_L-1)
n_L-1 > n-2-n_L+1
n_L-1 > (n-n_L)-1

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 ze zbioru 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:

Jeśli zbiór posiada lidera, to usunięcie z niego wszystkich par elementów różnych daje zbiór zawierający tylko elementy będące liderem.
Jeśli w wyniku takiej operacji otrzymujemy jednak zbiór pusty, to lidera w zbiorze wejściowym nie było.

Zamiast faktycznie wyrzucać ze zbioru 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\) ustawiamy 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 ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli zbiór \(Z\) posiadał 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 zbiorze \(Z\). Jeśli jest ona większa od liczby połowy elementów, to mamy lidera. W przeciwnym razie zbiór \(Z\) nie posiada lidera.

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

Algorytm wyszukiwania lidera w zbiorze

Wejście:

\(n\) : liczba elementów w tablicy \(Z\); \({n \in \mathbb{N}}\).
\(Z\) : tablica do wyszukania najczęstszego elementu. Elementy są liczbami całkowitymi. Indeksy od 0 do \({n-1}\).

Wyjście:

Element będący liderem, liczba jego wystąpień w \(Z\) lub informacja o braku lidera.

Elementy pomocnicze:

\(i\) : przebiega przez kolejne indeksy elementów \(Z\); \({i \in \mathbb{Z}}\).
\(L\) : licznik wystąpień wartości równych; \({L \in \mathbb{Z}}\).
\(W\) : wartość lidera.

Lista kroków:

K01: L ← 0 ; licznik wartości równych
K02: Dla i = 0, 1, …, n-1: ; przeglądamy kolejne elementy
     wykonuj kroki K03…K07
K03:   Jeśli L > 0, ; sprawdzamy, czy licznik równy 0
       to idź do kroku K07
K04:   W ← Z[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 = Z[i], ; elementy równe zliczamy
       to L ← L+1
       inaczej L ← L-1 ; elementy różne wyrzucamy
K08: Jeśli L = 0,        ; sprawdzamy, czy jest
     to idź do kroku K15 ; kandydat na lidera
K09: L ← 0 ; jeśli tak, to sprawdzamy, 
           ; czy jest liderem
K10: Dla i = 0, 1, …, n-1: ; zliczamy jego wystąpienia
     wykonuj krok K11   ; w zbiorze
K11:   Jeśli Z[i] = W, 
       to L ← L+1
K12: Jeśli L ≤ [n:2], ; lider?
     to idź do kroku K15
K13: Pisz W, L ; wyprowadzamy lidera oraz
              ; liczbę jego wystąpień
K14: Zakończ
K15: Pisz "BRAK LIDERA"
K16: 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 0 do 99 w taki sposób, aby mógł się pojawić w niej lider. Następnie program wyszukuje lidera podanym powyżej algorytmem, wyświetla zawartość tablicy z zaznaczonym liderem i wypisuje jego wartość oraz liczbę wystąpień. Jeśli pomimo wszystko zdarzy się, iż w tablicy \(Z\) nie będzie lidera, program wypisze tekst BRAK LIDERA.

Pascal

// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 80;

var
  Z : array [0..N-1] of integer;
  i, L, W : integer;
  t : boolean;

begin
  randomize;

  // Wypełniamy tablicę
  W := random(100);
  for i := 0 to N-1 do
    if random(2) = 1 then
      Z[i] := random(100)
    else
      Z[i] := W;

  // Wyszukujemy lidera
  L := 0;
  for i := 0 to N-1 do
    if L = 0 then
    begin
      W := Z[i]; L := 1;
    end
    else
      if W = Z[i] then
        inc(L)
      else
        dec(L);

  // Sprawdzamy, czy mamy lidera
  if L = 0 then
    t := false
  else
  begin
    L := 0;
    for i := 0 to N-1 do
      if W = Z[i] then
        inc(L);
    t := L > N div 2;
  end;

  // Wyświetlamy tablicę
  for i := 0 to N-1 do
    if t and (Z[i] = W) then
      write (' >', Z[i]:2)
    else
      write (Z[i]:4);

  // Wyświetlamy wyniki
  writeln;
  if t then
    writeln(W, ' : ', L)
  else
    writeln('BRAK LIDERA');
  writeln

end.

C++

// Wyszukiwanie lidera
// Data:   4.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], i, L, W;
  bool t;

  srand(time(NULL));

  // Wypełniamy tablicę
  W = rand() % 100;
  for(i = 0; i < N; i++)
    if(rand() % 2)
      Z[i] = rand() % 100;
    else
      Z[i] = W;

  // Wyszukujemy lidera
  L = 0;
  for(i = 0; i < N; i++)
    if(!L)
    {
      W = Z[i]; L = 1;
    }
    else
      if(W == Z[i])
        L++;
      else
        L--;

  // Sprawdzamy, czy mamy lidera
  if(!L) t = false;
  else
  {
    L = 0;
    for(i = 0; i < N; i++)
      if(W == Z[i])
        L++;
    t = L > N/2;
  }

  // Wyświetlamy tablicę
  for(i = 0; i < N; i++)
    if(t && (Z[i] == W))
      cout << " >" << setw(2) << Z[i];
    else
      cout << setw(4) << Z[i];

  // Wyświetlamy wyniki
  cout << endl;
  if(t)
    cout << W << " : " << L << endl;
  else
    cout << "BRAK LIDERA\n";
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie lidera
' Data:   4.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 80

Dim As Integer Z(N-1), i, L, W, t

Randomize

' Wypełniamy tablicę
W = Cint(Rnd*99)
For i = 0 To N-1
  If Rnd > 0.5 Then
    Z(i) = Cint(Rnd*99)
  Else
    Z(i) = W
  End If
Next

' Wyszukujemy lidera
L = 0
For i = 0 To N-1
  If L = 0 Then
    W = Z(i): L = 1
  Elseif W = Z(i) Then
    L += 1
  Else
    L -= 1
  End If
Next

' Sprawdzamy, czy mamy lidera
If L = 0 Then
  t = 0
Else
  L = 0
  For i = 0 To N-1
    If W = Z(i) Then L += 1
  Next
  t = (L > N\2)
End If

' Wyświetlamy tablicę
For i = 0 To N-1
  If t And (Z(i) =  W) Then
    Print Using " >##";Z(i);
  Else
    Print Using "####";Z(i);
  End If
Next

' Wyświetlamy wyniki
Print
If t Then
  Print W;" : ";L
Else
  Print "BRAK LIDERA"
End If
Print
End

Python (dodatek)

# Wyszukiwanie lidera
# Data:  26.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 80
z = []

# Wypełniamy tablicę
r = random.randrange(100)
for i in range(N):
    if random.randrange(2):
        z.append(random.randrange(100))
    else:
        z.append(r)

# Wyszukujemy lidera
c = 0
for i in range(N):
    if c == 0:
        r, c = z[i], 1
    elif r == z[i]:
        c += 1
    else:
        c -= 1
# Sprawdzamy, czy mamy lidera
if c == 0:
    t = False
else:
    c = 0
    for i in range(N):
        if r == z[i]: c += 1
    t = (c > N//2)
# Wyświetlamy tablicę
for i in range(N):
    if t and (z[i] ==  r):
        print(" >%2d" % z[i], end="")
    else:
        print("%4d" % z[i], end="")
# Wyświetlamy wyniki
print()
if t:
    print(r, ":", c)
else:
    print("BRAK LIDERA")
print()

Wynik:

  74   9  72  72  72  39  20  72  98  54  71  90  72  47  73  72  72  72  72  58
  92  36  72  23  79  36  72  72  15  90  13  72  97  72  72  76  91  87  72  62
  42  72  82  95  72  51  72  74  72  72  98  72  72  72  30  72  94  92  28  72
  72  20  74  72  43   7  72  52  85  72  38   2  72  72  72  72  72  29   5  49
BRAK LIDERA

  33  52  41 >83  20 >83 >83 >83 >83 >83 >83  17  58  11  98 >83  87 >83 >83  71
  57 >83  31  17 >83 >83 >83 >83 >83 >83  63  16 >83  46 >83 >83 >83 >83  41  61
  41  68  98 >83  47  65 >83 >83 >83 >83  59 >83 >83 >83  23 >83 >83 >83 >83 >83
  14 >83  70  10 >83 >83 >83   5 >83 >83  66 >83 >83 >83  53  91 >83 >83   2 >83
83 : 47

JavaScript

<html>
  <head>
    <title>
      Lider
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Wyszukiwanie lidera</b>
          <br/>
          &nbsp;&nbsp;
          (C)2026 mgr
          Jerzy Wałaszek&nbsp;
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------


function main()
{
  var N = 120;
  var Z = Array(N);
  var c,i,L,W,t,s;

  // Wypełniamy tablicę
  W = Math.floor(
      Math.random() * 100);
  for(i = 0; i < N; i++)
    if(Math.random() > 0.5)
      Z[i] = Math.floor(
             Math.random() * 100);
    else
      Z[i] = W;

  // Wyszukujemy lidera
  L = 0;
  for(i = 0; i < N; i++)
    if(!L)
    {
      W = Z[i];
      L = 1;
    }
    else if(W == Z[i]) L++;
    else L--;

  // Sprawdzamy, czy mamy lidera
  if(!L) t = false;
  else
  {
    L = 0;
    for(i = 0; i < N; i++)
      if(W == Z[i]) L++;
    t = L>N / 2;
  }

  // Wyświetlamy tablicę

  s = "<pre class='small'>";
  c = 0;
  for(i = 0; i < N; i++)
  {
    if(Z[i] < 10) s += " "
    if(t && (Z[i] == W))
      s += "<span style='color:red'>" +
           "<b> " + Z[i] + 
           "</b></span>";
    else
      s += " " + Z[i];
    c++;
    if(c == 15)
    {
      c = 0;
      s += " <br/>";
    }
  }

  // Wyświetlamy wyniki
  s += "</pre>";
  if(t)
    s += "<span style='color:red'>" +
         W + "</span> : " + L;
  else
    s += "<span style='color:red'>" +
         "<b>BRAK LIDERA</b></span>";
  document.getElementById("out")
  .innerHTML = s;
}

</script>

  </body>
</html>

do podrozdziału do strony

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.

Wyszukiwanie lidera