Wyszukiwanie lidera


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

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

 

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 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, 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 wykonuj K03...K07 ; przeglądamy kolejne elementy
K03:     Jeśli L > 0, to idź do K07 ; sprawdzamy, czy licznik równy 0
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], to LL + 1
    inaczej LL - 1
; elementy równe zliczamy
; elementy różne wyrzucamy
K08: Jeśli L = 0, to idź do 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 K11 ; zliczamy jego wystąpienia w zbiorze
K11:     Jeśli Z[i] = W, to LL + 1  
K12: Jeśli L ≤ [n:2], to idź do K15 ; lider?
K13 Pisz W,L ; wyprowadzamy lidera oraz liczbę jego wystąpień
K14: Zakończ  
K15: Pisz "BRAK LIDERA"  
K16: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie lidera
// Data:   4.05.2008
// (C)2012 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[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;
}
Free Basic
' Wyszukiwanie lidera
' Data:   4.05.2008
' (C)2012 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
  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)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.