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 pn
ln - liczba wystąpień najczęstszego elementu, ln Zmienne pomocnicze
i, j - zmienne licznikowe pętli. i, j licznik - licznik wystąpień elementu
krok 1: wn d[1]; pn
krok 2: Dla i = 1,2,...,n: wykonuj kroki 3...5 krok 3: licznik krok 4: Dla j = 1,2,...,n: jeśli d[i] = d[j], to licznik krok 5: Jeśli licznik > ln , to wn 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 |
// 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"
# 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 "wn = %d, pn = %d, ln = %d" % (wn, pn + 1, ln)
# 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="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 += " " + 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.
Źródło: mgr Jerzy Wałaszek