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

©2020 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 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 posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. Zatem licznik L  powinien mieć zawartość większą od zera. Jeśli zawartość licznika L  jest równa zero, to lidera w zbiorze nie ma. W przeciwnym razie zapamiętany element należy przeliczyć w zbiorze – jest to kandydat na lidera. Jeśli liczba jego wystąpień jest większa od liczby połowy elementów, to wytypowany element jest liderem. 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, nN.
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. iC.
L  – licznik wystąpień wartości równych, LC.
W  – wartość lidera.

Lista kroków:

K01: L  ← 0 licznik wartości równych
K02: Dla i  = 0, 1, ..., n-1:
wykonuj kroki K03...K07
przeglądamy kolejne elementy
K03:     Jeśli L  > 0,
    to idź do kroku K07
sprawdzamy, czy licznik równy 0
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  ],
    to L  ← L  + 1
    inaczej L  ← L  - 1
elementy równe zliczamy elementy różne wyrzucamy
K08: Jeśli L  = 0,
to idź do kroku K15
sprawdzamy, czy jest kandydat na lidera
K09: L  ← 0 jeśli tak, to sprawdzamy, czy jest liderem
K10: Dla i  = 0, 1, ..., n-1:
wykonuj krok K11
zliczamy jego wystąpienia w zbiorze
K11:     Jeśli Z [ i  ] = W,
    to L  ← L  + 1
 
K12: Jeśli L  ≤ [ n:2 ],
to idź do kroku K15
lider?
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 <time.h>

using namespace std;

const int N = 80;

int main( )
{
  int Z [ N ], i, L, W;
  bool t;

  srand ( ( unsigned )time ( NULL ) );

  // Wypełniamy tablicę

  W = rand( ) % 100;
  for( i = 0; i < N; i++ )
    if( rand( ) % 2 ) Z [ i ] = rand( ) % 100;
    else              Z [4 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
Wynik:
xxx

  47  32  47  38  47  40  64  28  47  47  11  47  47  52  46  65  47  47  47  73
  47  35   6   4  42  83  17  47  51  47  47  47  47  47  47  90  47  47  47  47
  64  41  47  53  22  47  47  68  47  86  47  47  47  94  47  47  89  47  47  49
  63  47  13  47  76  47  47  31  60  98  30  32  47   3  47  54  59  47  93  62

BRAK LIDERA


 >37  46  80 >37 >37 >37 >37 >37  95  46 >37  17 >37  86 >37  30 >37 >37  70  33
 >37 >37  77  20  24 >37  79   6 >37  65  88 >37  13 >37 >37  51 >37   6 >37  77
 >37  66  99  20 >37  34 >37  94 >37  10  48 >37 >37 >37 >37  34 >37 >37  14  64
  79 >37  56 >37 >37 >37 >37  96  47  10 >37 >37 >37 >37 >37 >37  68 >37 >37 >37

37 : 44
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
©2020 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.