Algorytmy wyszukujące - wyszukiwanie lidera

Liderem będziemy nazywać element zbioru występujący w nim więcej niż [ⁿ/₂] razy, gdzie n oznacza ilość elementów zbiorze. Innymi słowy liderem jest element, którego liczba wystąpień jest większa, od sumy liczby wystąpień pozostałych elementów.

W zbiorze { 9 2 9 5 9 7 9 } liderem jest 9, ponieważ 9 występuje w zbiorze 4 razy, a wszystkie pozostałe elementy występują w sumie 3 razy.

Narzucającym się rozwiązaniem tego problemu jest znalezienie lidera przy pomocy wcześniej opisanych algorytmów wyszukiwania najczęściej pojawiającego się elementu. Można to wykonać w sposób następujący:

Wyszukujemy najczęściej występujący element. Sprawdzamy, czy ilość jego wystąpień jest większa od  [n/2]. Jeśli tak, znaleźliśmy lidera. W przeciwnym razie lider w zbiorze nie występuje.

Algorytm posiada klasę czasowej złożoności obliczeniowej O(n²) lub O(n + m) w zależności od wyboru algorytmu wyznaczającego najczęstszy element zbioru.

		Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

Program wypełnia 20 elementowy zbiór pseudolosowymi liczbami z zakresu od 0 do 9, a następnie poszukuje w nim lidera.

Wyszukiwanie lidera - wersja nr 1
---------------------------------
   (C)2006  mgr Jerzy Wałaszek
         I LO w Tarnowie

  0  <9>  5  <9> <9> <9> <9>  5  <9>  6  <9>  2   2  <9> <9> <9> <9> <9> <9>  0

lider = 9, ln = 13

KONIEC. Naciśnij dowolny klawisz...

Wyszukiwanie lidera - wersja nr 1
---------------------------------
   (C)2006  mgr Jerzy Wałaszek
         I LO w Tarnowie

  4   8   4   7   1   8   4   5   2   5   4   1   4   4   1   4   5   3   4   4

W zbiorze nie ma lidera

KONIEC. Naciśnij dowolny klawisz...

//     Wyszukiwanie lidera
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
//      I LO w Tarnowie
//----------------------------

program searchleader;

{$APPTYPE CONSOLE}

const
  N    = 20;  // liczba elementów w zbiorze
  WMAX =  9;  // górny zakres elementów

var
  d                 : array[1..N] of integer;
  i,j,licznik,ln,wn : cardinal;
  wt                : boolean;
begin
  writeln('Wyszukiwanie lidera - wersja nr 1');
  writeln('---------------------------------');
  writeln('   (C)2006  mgr Jerzy Walaszek   ');
  writeln('         I LO w Tarnowie         ');
  writeln;

// Generujemy zbiór liczb pseudolosowych

  randomize;
  wn := random(WMAX + 1);
  for i := 1 to N do d[i] := wn;
  for i := 1 to 3 + N div 2 do d[1 + random(N)] := random(WMAX + 1);

// Wyszukujemy najczęstszy element

  wn := d[1]; ln := 1;
  i := 1;
  while i <= N - ln do
  begin
    licznik := 1;
    for j := i + 1 to N do if d[i] = d[j] then inc(licznik);
    if licznik > ln then
    begin
      wn := d[i]; ln := licznik;
    end;
    inc(i);
  end;
  wt := (ln > N div 2);

// Prezentujemy wyniki

  for i := 1 to N do
    if wt and (wn = d[i]) then
      write(' <', d[i], '>')
    else
      write('  ', d[i], ' ');
  writeln;
  if wt then
    writeln('lider = ', wn, ', ln = ', ln)
  else
    writeln('W zbiorze nie ma lidera');
  writeln;

// Gotowe

  writeln('Nacisnij klawisz Enter...');
  readln;
end.

//     Wyszukiwanie lidera
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
//      I LO w Tarnowie
//----------------------------

#include <iostream>

using namespace std;

const int N    = 20;  // liczba elementów w zbiorze
const int WMAX =  9;  // górny zakres elementów

int main(void)
{
  int d[N];
  unsigned i,j,licznik,ln,wn;
  bool wt;

  cout << "Wyszukiwanie lidera - wersja nr 1\n"
          "---------------------------------\n"
          "   (C)2006  mgr Jerzy Walaszek   \n"
          "         I LO w Tarnowie         \n\n";

// Generujemy zbiór liczb pseudolosowych

  srand((unsigned)time(NULL));
  wn = rand() % (WMAX + 1);
  for(i = 0; i < N; i++) d[i] = wn;
  for(i = 1; i <= 3 + N / 2; i++) d[rand() % N] = rand() % (WMAX + 1);

// Wyszukujemy najczęstszy element

  wn = d[0]; ln = 1;
  for(i = 0; i < N - ln; i++)
  {
    licznik = 1;
    for(j = i + 1; j < N; j++) if(d[i] == d[j]) licznik++;
    if(licznik > ln)
    {
      wn = d[i]; ln = licznik;
    }
  }
  wt = (ln > N / 2);

// Prezentujemy wyniki

  for(i = 0; i < N; i++)
    if(wt && (wn == d[i]))
      cout << " <" << d[i] << ">";
    else
      cout << "  " << d[i] << " ";
  cout << endl;
  if(wt)
    cout << "lider = " << wn << ", ln = " << ln;
  else
    cout << "W zbiorze nie ma lidera";
  cout << endl << endl;

// Gotowe

  system("pause"); return 0;
}

'     Wyszukiwanie lidera
'----------------------------
' (C)2006 mgr Jerzy Wałaszek
'      I LO w Tarnowie
'----------------------------

Module Module1

  Sub Main()
    Const N = 20 ' liczba elementów w zbiorze
    Const WMAX = 9 ' górny zakres elementów

    Dim d(N) As Integer
    Dim i, j, licznik, ln, wn As UInteger
    Dim wt As Boolean

    Console.WriteLine("Wyszukiwanie lidera - wersja nr 1")
    Console.WriteLine("---------------------------------")
    Console.WriteLine("   (C)2006  mgr Jerzy Wałaszek   ")
    Console.WriteLine("         I LO w Tarnowie         ")
    Console.WriteLine()

    ' Generujemy zbiór liczb pseudolosowych

    Randomize()
    wn = Int(Rnd(1) * (WMAX + 1))
    For i = 1 To N : d(i) = wn : Next
    For i = 1 To 3 + N \ 2
      d(Int(Rnd(1) * N) + 1) = Int(Rnd(1) * (WMAX + 1))
    Next

    ' Wyszukujemy najczęstszy element

    wn = d(1) : ln = 1 : i = 1
    While i <= N - ln
      licznik = 1
      For j = i + 1 To N
        If d(i) = d(j) Then licznik += 1
      Next
      If licznik > ln Then
        wn = d(i) : ln = licznik
      End If
      i += 1
    End While
    wt = ln > N \ 2

    ' Prezentujemy wyniki

    For i = 1 To N
      If wt AndAlso (wn = d(i)) Then
        Console.Write(" <{0}>", d(i))
      Else
        Console.Write("  {0} ", d(i))
      End If
    Next
    Console.WriteLine()
    If wt Then
      Console.WriteLine("lider = {0}, ln = {1}", wn, ln)
    Else
      Console.WriteLine("W zbiorze nie ma lidera")
    End If

    ' Gotowe

    Console.WriteLine()
    Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
    Console.ReadLine()

  End Sub

End Module

# -*- coding: cp1250 -*-
#     Wyszukiwanie lidera
#----------------------------
# (C)2006 mgr Jerzy Wałaszek
#      I LO w Tarnowie
#----------------------------

import random

N    = 20 # liczba elementów w zbiorze
WMAX =  9 # górny zakres elementów

d = [ ]

print "Wyszukiwanie lidera - wersja nr 1"
print "---------------------------------"
print "   (C)2006  mgr Jerzy Walaszek   "
print "         I LO w Tarnowie         "
print

# Generujemy zbiór liczb pseudolosowych

wn = random.randint(0, WMAX)
for i in range(N): d.append(wn)
for i in range(4 + N / 2):
  d[random.randint(0, N - 1)] = random.randint(0, WMAX)

# Wyszukujemy najczęstszy element

wn, ln, i = d[0], 1, 0
while i < N - ln:
  licznik = 1
  for j in range(i + 1, N):
    if d[i] == d[j]: licznik += 1
  if licznik > ln: wn, ln = d[i], licznik
  i += 1
wt = (ln > N / 2)

# Prezentujemy wyniki

for i in d:
  if wt and (wn == i):
    print " <%d>" % i,
  else:
    print "  %d " % i,
print
print
if wt:
  print "lider = %d, ln = %d" % (wn, ln)
else:
  print "W zbiorze nie ma lidera"
print
print

# Gotowe

raw_input("Koniec, nacisnij dowolny klawisz...")

<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66" name="frmSearchLD">
        <h4 style="TEXT-ALIGN: center">
          Wyszukiwanie lidera w zbiorze
        </h4>
        <p style="TEXT-ALIGN: center">
          (C)2006 mgr Jerzy Wałaszek<br>
          I LO w Tarnowie
        </p>
        <hr>
        <p style="TEXT-ALIGN: center">
          <input type="button" value="Szukaj" name="B1" onclick="main();">
        </p>
        <p style="TEXT-ALIGN: center" id="t_out">...</p>
      </form>

<script language=javascript>

// Wyszukiwanie lidera
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

function main()
{
  var N    = 20; // liczba elementów w zbiorze
  var WMAX =  9; // górny zakres elementów
  var d = new Array(N);
  var i,j,licznik,ln,wn,wt,t;

// Generujemy zbiór liczb pseudolosowych

  wn = Math.floor(Math.random() * (WMAX + 1));
  for(i = 0; i < N; i++) d[i] = wn;
  for(i = 1; i <= 3 + Math.floor(N / 2); i++)
    d[Math.floor(Math.random() * N)] = Math.floor(Math.random() * (WMAX + 1));

// Wyszukujemy najczęstszy element

  wn = d[0]; ln = 1;
  for(i = 0; i < N - ln; i++)
  {
    licznik = 1;
    for(j = i + 1; j < N; j++) if(d[i] == d[j]) licznik++;
    if(licznik > ln)
    {
      wn = d[i]; ln = licznik;
    }
  }
  wt = (ln > Math.floor(N / 2));

// Prezentujemy wyniki

  t = "";
  for(i = 0; i < N; i++)
    if(wt && (wn == d[i]))
      t += " <b><font color=red>&lt;" + d[i] + "></font></b>";
    else
      t += " &nbsp;" + d[i] + "&nbsp;";
  t += "<BR><BR>";
  if(wt)
    t += "lider = " + wn + ", ln = " + ln;
  else
    t += "<font color=blue>W zbiorze nie ma lidera</font>";

// Gotowe

  document.getElementById("t_out").innerHTML = t;
}

</script>

    </div>
  </body>
</html>

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

Źródło: mgr Jerzy Wałaszek