Login lub e-mail Hasło   

Algorytmy wyszukujące - najczęstszy element

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Zadanie jest następujące: W n elementowym zbiorze znaleźć element, który powtarza się najczęściej Pierwszym, narzucającym si...
Wyświetlenia: 3.917 Zamieszczono 03/11/2006

Zadanie jest następujące:

W n elementowym zbiorze znaleźć element, który powtarza się najczęściej

Pierwszym, narzucającym się rozwiązaniem jest podejście bezpośrednie. Wybieramy ze zbioru kolejne elementy i zliczamy ich wystąpienia. Wynikiem jest element, który występował najczęściej. Policzmy czasową złożoność obliczeniową takiego algorytmu:

Wybór n elementów wymaga n operacji. Po każdym wyborze musimy wykonać n porównań wybranego elementu z elementami zbioru w celu zliczenia ilości jego wystąpień. Daje to wynik:

T(n) = n2

Zatem algorytm w tej postaci posiada klasę złożoności O(n2). W dalszych rozdziałach zastanowimy się nad sposobami poprawy tego wyniku. (Zadanie o podobnej treści pojawiło się na maturze z informatyki w 2006 roku).

Dane wejściowe

n - ilość elementów w przeszukiwanym zbiorze.  n N
d[ ] - zbiór, w którym poszukujemy najczęstszego elementu.

Dane wyjściowe

wn - wartość elementu powtarzającego się najczęściej.
pn - pierwsza pozycja elementu najczęstszego. pn N,   1 pn n
ln - liczba wystąpień najczęstszego elementu, ln N,   1 ln n

Zmienne pomocnicze

i, j - zmienne licznikowe pętli. i, j N
licznik - licznik wystąpień elementu
krok 1: wn d[1];  pn 1;  ln 1
krok 2: Dla i = 1,2,...,n: wykonuj kroki 3...5
krok 3:     licznik 0
krok 4:     Dla j = 1,2,...,n:  jeśli d[i] = d[j],  to  licznik licznik + 1
krok 5:     Jeśli licznik > ln ,  to   wn d[i];  pn iln licznik
krok 6: Zakończ algorytm

Algorytm wyszukiwania najczęściej pojawiającego się elementu w zbiorze rozpoczynamy od inicjalizacji zmiennych, których zawartość będzie wynikiem pracy algorytmu.

Do wn trafia pierwszy element zbioru - tymczasowo będzie to najczęstszy element. W pn umieszczamy pozycję tego elementu, czyli 1. Do ln zapisujemy liczbę wystąpień, też 1.

Rozpoczynamy pętlę nr 1, która wybiera ze zbioru kolejne elementy. W zmiennej licznik będziemy zliczać ilość wystąpień elementu d[i]. Dokonuje tego wewnętrzna pętla nr 2, która przegląda kolejne elementy zbioru i jeśli są równe elementowi d[i], zwiększa o 1 stan licznika. Po zakończeniu tej pętli w zmiennej licznik mamy liczbę wystąpień w zbiorze elementu d[i].

Jeśli licznik zawiera wartość większą od ilości powtórzeń tymczasowego elementu ln, to za nowy tymczasowy element przyjmujemy d[i]. Do wn trafia wartość elementu, do pn zapisujemy numer jego pozycji, czyli i, a do ln zapisujemy wyznaczoną w zmiennej licznik liczbę powtórzeń.

Na końcu pętli nr 1 zwiększamy i o 1, czyli przechodzimy do kolejnego elementu w zbiorze i operację zliczania powtarzamy.

Po zakończeniu pętli nr 1 w zmiennej wn mamy wartość najczęściej powtarzającego się elementu, w pn jest pozycja jego pierwszego pojawienia się w zbiorze, a w ln mamy wyznaczoną ilość wystąpień.

Algorytm jest bardzo prosty w działaniu, lecz mało efektywny - niektóre elementy są zliczane wielokrotnie, a niektóre zupełnie niepotrzebnie. Usuwając te wady usprawnimy algorytm, co jest celem następnego rozdziału. W programowaniu często obowiązuje zasada:

Efektywność algorytmu jest odwrotnie proporcjonalna do jego złożoności. Wynika stąd, iż proste algorytmy mogą być mało efektywne, podczas gdy algorytmy złożone działają bardzo szybko pomijając operacje zbędne.

Jednakże dla małej ilości danych (do 5000) przedstawione rozwiązanie jest całkiem skuteczne i, ze względu na swą prostotę, warte stosowania.

   
   
   

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 generuje zbiór 100 liczb pseudolosowych z zakresu od 0 do 9, a następnie wyszukuje wśród nich liczbę powtarzającą się najczęściej.

Efekt uruchomienia programu
Demonstracja wyszukiwania najczęstszego elementu
------------------------------------------------
(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie

5 0 (4) 8 1 7 8 8 6 0 2 9 9 0 (4) (4) (4) 3 (4) 0
9 8 7 3 3 5 2 8 2 6 (4) 5 (4) 1 6 1 (4) 2 3 0
6 1 (4) 9 1 7 9 8 1 2 9 6 9 5 0 7 1 (4) 5 5
2 (4) (4) 8 1 5 3 3 2 (4) 6 6 5 8 0 8 2 1 6 1
3 3 1 2 2 1 9 9 0 3 1 6 (4) 5 5 8 8 0 0 5

wn = 4, pn = 3, ln = 14

KONIEC. Naciśnij dowolny klawisz...

// Wyszukiwanie najczęstszego elementu
//-------------------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//-------------------------------------

program searchmf1;

{$APPTYPE CONSOLE}

const

N = 100; // liczba elementów w zbiorze
M = 9; // górny zakres elementów

var
d : array[1..N] of cardinal;
i,j,licznik,ln,pn,wn : cardinal;

begin
writeln('Demonstracja wyszukiwania najczestszego elementu');
writeln('------------------------------------------------');
writeln('(C)2006 mgr Jerzy Walaszek I LO w Tarnowie');
writeln;

// Generujemy zbiór liczb pseudolosowych

randomize;
for i := 1 to N do d[i] := random(M + 1);

// Wyszukujemy najczęstszy element

wn := d[1]; pn := 1; ln := 1;
for i := 1 to N do
begin

licznik := 0;
for j := 1 to N do if d[i] = d[j] then inc(licznik);
if licznik > ln then
begin

wn := d[i]; pn := i; ln := licznik;
end;
end;

// Prezentujemy wyniki

for i := 1 to N do
if
d[i] = wn then write(' (', d[i], ')') else write(' ', d[i], ' ');
writeln;
writeln('wn = ', wn, ', pn = ', pn, ', ln = ', ln);

// Gotowe

writeln;
writeln('Koniec, nacisnij klawisz Enter...');
readln;
end.
// Wyszukiwanie najczęstszego elementu
//-------------------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//-------------------------------------

#include <iostream>

using namespace std;

const int N = 100; // liczba elementów w zbiorze
const int M = 9; // górny zakres elementów

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

cout << "Demonstracja wyszukiwania najczestszego elementu\n"
"------------------------------------------------\n"
"(C)2006 mgr Jerzy Walaszek I LO w Tarnowie\n\n"
;

// Generujemy zbiór liczb pseudolosowych

srand((unsigned)time(NULL));
for(i = 0; i < N; i++) d[i] = rand() % (M + 1);

// Wyszukujemy najczęstszy element

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

// Prezentujemy wyniki

for(i = 0; i < N; i++)
if(d[i] == wn)
cout << " (" << d[i] << ")";
else
cout << " " << d[i] << " ";
cout << "\nwn = " << wn << ", pn = " << pn + 1 << ", ln = " << ln << "\n\n";

// Gotowe

system("pause"); return 0;
}
' Wyszukiwanie najczęstszego elementu
'-------------------------------------
' (C)2006 mgr Jerzy Wałaszek
' I LO w Tarnowie
'-------------------------------------

Module Module1

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

Dim d(N), i, j, licznik, ln, pn, wn As UInteger

Console.WriteLine("Demonstracja wyszukiwania najczęstszego elementu")
Console.WriteLine("------------------------------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie")
Console.WriteLine()

' Generujemy zbiór liczb pseudolosowych

Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

' Wyszukujemy najczęstszy element

wn = d(1) : pn = 1 : ln = 1
For i = 1 To N
licznik = 0
For j = 1 To N
If d(i) = d(j) Then licznik += 1
Next
If
licznik > ln Then
wn = d(i) : pn = i : ln = licznik
End If
Next


' Prezentujemy wyniki

For i = 1 To N
If d(i) = wn Then
Console.Write(" ({0})", d(i))
Else
Console.Write(" {0} ", d(i))
End If
Next

Console.WriteLine()
Console.WriteLine("wn = {0}, pn = {1}, ln = {2}", wn, pn, ln)
Console.WriteLine()

' Gotowe

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

End Sub

End Module
# -*- coding: cp1250 -*-
# Wyszukiwanie najczęstszego elementu
#-------------------------------------
# (C)2006 mgr Jerzy Wałaszek
# I LO w Tarnowie
#-------------------------------------

import random

N = 100 # liczba elementów w zbiorze
M = 9 # górny zakres elementów

d = []

print "Demonstracja wyszukiwania najczestszego elementu"
print "------------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek I LO w Tarnowie"
print

# Generujemy zbiór liczb pseudolosowych

for i in range(N): d.append(random.randint(0, M))

# Wyszukujemy najczęstszy element

wn, pn, ln = d[0], 0, 1
for i in range(N):
licznik = d.count(d[i])
if licznik > ln:
wn, pn, ln = d[i], i, licznik

# Prezentujemy wyniki

for i in d:
if i == wn:
print " (%d)" % i,
else:
print " %d " % i,
print
print

print "wn = %d, pn = %d, ln = %d" % (wn, pn + 1, ln)

# Gotowe

print
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="frmSearchMF">
<h4 id=
"out_t" style="TEXT-ALIGN: center">
Demonstracja wyszukiwania najczęstszego elementu
</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 najczęstszego elementu
//-------------------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//-------------------------------------

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

// Generujemy zbiór liczb pseudolosowych

for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Wyszukujemy najczęstszy element

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

// Prezentujemy wyniki

t = "";
for(i = 0; i < N; i++)
if(d[i] == wn)
t += "<b><font color=red>(" + d[i] + ")</font></b> ";
else
t += " &nbsp;" + d[i] + " ";
t += "<br><br>wn = " + wn + ", pn = " + (pn + 1) + ", ln = " + ln;

// Gotowe

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

</script>
</div>
</body>
</html>
 
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6262
16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64977
12
komentarze: 3 | wyświetlenia: 29779
37
komentarze: 9 | wyświetlenia: 28520
11
komentarze: 2 | wyświetlenia: 33152
18
komentarze: 11 | wyświetlenia: 9268
7
komentarze: 1 | wyświetlenia: 34649
17
komentarze: 4 | wyświetlenia: 14181
15
komentarze: 5 | wyświetlenia: 32761
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 1 | wyświetlenia: 86405
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska