JustPaste.it

Algorytmy wyszukujące - wyszukiwanie lidera

56dd2de517933ae433d604e40eeaf7b7.gif

Liderem będziemy nazywać element zbioru występujący w nim więcej niż [n/2] 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.

fe1e504093adcb462e03b8bff4167a7b.gif

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(n2) lub O(n + m) w zależności od wyboru algorytmu wyznaczającego najczęstszy element zbioru.

dea55ef580e288b29d44a1e0f621a0e1.gif

4c09e8e8bea3d22a24711fa6de801142.gif    
   
   

ad1a04d9b7e7844569648f2cfc51e435.gif

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.

Efekt uruchomienia programu
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...

7fbc56e52afdb301ba86bc7093d0b227.gif
//     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.
aeba724970c6c603059f6b381701dce9.gif
//     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;
}
51c6bd4afd82515dcd8175b5a842d81c.gif
'     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
cb892092387ece8bedb743eaf2cb211d.gif
# -*- 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...")
1ccfc69efb2b6f0f7a807832a4889730.gif
<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