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 lidera

SPIS TREŚCI
Tematy pomocnicze

Problem

W n-elementowym zbiorze Z należy wyszukać element, którego wartość występuje więcej niż n/2 razy.

Rozwiązanie

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 nL liczbę elementów będących liderami. Zbiór Z posiada n elementów, zatem liczba pozostałych elementów wynosi n - nL. Zachodzi nierówność:

nL> n - nL

Przypadek 1

Ze zbioru Z usuwamy dwa elementy, które nie są liderami. W tym przypadku nL 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ż nL 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:

nL - 1 > (n - 2)  - (nL - 1)
nL - 1 >  n - 2   -  nL + 1
nL - 1 > (n - nL) - 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 ∈ 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.

Zmienne pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
L : licznik wystąpień wartości równych, L ∈ C.
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:   WZ[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 LL + 1
       inaczej LL - 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 LL + 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ę

W = random.randrange(100)
for i in range(N):
    if random.randrange(2):
        Z.append(random.randrange(100))
    else:
        Z.append(W)

# Wyszukujemy lidera

L = 0
for i in range(N):
    if L == 0:
        W, L = Z[i], 1
    elif W == Z[i]:
        L += 1
    else:
        L -= 1

# Sprawdzamy, czy mamy lidera

if L == 0:
    t = false
else:
    L = 0
    for i in range(N):
        if W == Z[i]: L += 1
    t = (L > N//2)

# Wyświetlamy tablicę

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

# Wyświetlamy wyniki

print()
if t:
    print(W,":",L)
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
Wyszukiwanie lidera
(C)2020 mgr Jerzy Wałaszek


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.