Programowanie i algorytmy

Znajdowanie lidera w zbiorze

powrót

Lider to taka wartość w zbiorze {tex}n{/tex} elementów, która powtarza się więcej niż {tex}n\ div\ 2{/tex} razy. Jeśli istnieje taka wartość, to jest ona tylko jedna. Prześledźmy przykłady:

ciąg liczb

{tex}1, 3, 4, 3, 2 ,1 ,1{/tex}

nie posiada lidera, ponieważ żadna z liczb nie wystąpiła co najmniej {tex}7\ div\ 2 + 1 = 4{/tex} razy.

Ciąg

{tex}1, 2, 2, 3, 3 , 3, 3, 2{/tex}

także nie posiada lidera, natomiast dla  liczb

{tex}1, 2, 2, 3, 3 , 3, 3, 2, 3{/tex}

liderem jest liczba {tex}3{/tex}.

Strategia jest następująca. Przeszukujemy liniowo kolejne elementy i w danym etapie dwa różne elementy zbioru wykreślamy - tak jak by ich nie było. Jeśli lider występuje w zbiorze, to jego "pozycja" w otrzymanym podzbiorze się nie zmieni. Przeanalizujmy następujący przykład:

{tex}1, 2, 1, 3, 3 , 3, 3, 2, 3{/tex}

lider w zbiorze

i pozostał na zbiór, w którym nadal mamy lidera:

{tex}1, 3, 3 , 3, 3, 2, 3{/tex}

Redukując w ten sposób elementy dochodzimy do sytuacji, gdy pozostanie element, który jest kandydatem na lidera. Musimy teraz tylko liniowo zliczyć i sprawdzić, czy dana wartość występuje więcej niż {tex}n\ div\ 2{/tex} razy.

Warto podkreślić, że znaleziony element nie musi być liderem. Prześledźmy przykład, w którym nie ma lidera:

{tex}2, 3, 1, 1, 1, 4{/tex}

Po wykreśleniu dwóch początkowych wyrazów pozostaje podzbiór

{tex}1, 1, 1, 4{/tex},

w którym jest lider.

W programie przedstawionym poniżej ważną rolę odgrywa zmienna {tex}dopary{/tex}. Odpowiedzialna jest ona za kontrolowanie wykreślania dwóch elementów o różnych wartościach. Jeśli wykreślimy wszystkie elementy, oznacza to, że żadna wartość nie spełnia oczekiwań. Przeanalizujmy przypadek:

lider

W przypadku znalezienia liczby różnej od aktualnego lidera, wykreślamy ją zmniejszając wartość zmiennej {tex}dopary{/tex}. Gdy znajdziemy taką samą, wartość zmiennej inkrementujemy. Jeśli {tex}dopary{/tex} będzie liczbą większą od zera, oznacza to, że zmienna {tex}lider{/tex} przechowuje potencjalnego lidera zbioru.

Rozwiązanie w C++:

#include<iostream>
#include<cstdlib>
using namespace std;
 
int szukaj_lidera(int tab[],int n)
{
  int lider = tab[0], do_pary = 1;
 
  //wykreślanie par o różnych wartościach
  for(int i=1;i<n;i++)
  if(do_pary > 0)
    if(tab[i]==lider) 
      ++do_pary; 
    else
      --do_pary; 
  else
  {
    ++do_pary;
    lider = tab[i];
  }
  //koniec wykreślania
 
  if(do_pary==0)
    return -1; //zwrócenie -1 oznacza, że zbiór nie posiada lidera
 
  int ile = 0; //zmienna zliczająca wystąpieńia potencjalnego lidera
 
  for(int i=0;i<n;i++)  //zliczamy wystąpienia lidera
    if(tab[i]==lider) 
      ++ile;
 
  if(ile>n/2) //sprawdzamy, czy potencjalny lider występuje oczekiwaną ilość razy
    return lider;
 
  return -1;
}
 
int main()
{
  int n, *tab, lider;
 
  cout<<"Ile liczb chcesz wczytać? ";
  cin>>n;
 
  tab = new int [n];
 
  for(int i=0;i<n;i++)
    cin>>tab[i];
 
  lider = szukaj_lidera(tab,n);
 
  if(lider==-1)
    cout<<"Zbiór nie posiada lidera"<<endl;
  else
    cout<<"Liderem zbioru jest "<<lider<<endl;
 
  delete [] tab;  
 
  return 0;
}