Zadanie jest następujące:
W n elementowym zbiorze danych znaleźć element maksymalny i minimalny. Jeśli podejdziemy do tego zadania w sposób tradycyjny, to wyszukanie elementu maksymalnego będzie wymagało wykonania n - 1 porównań (porusz poprzedni rozdział). Podobnie jest dla elementu minimalnego. Zatem złożoność obliczeniowa problemu wyszukania elementu maksymalnego i minimalnego będzie równa:
T(n) = 2(n - 1) = 2n - 2
Czy można ten wynik poprawić? Okazuje się, że tak. Musimy zastosować zasadę Dziel i Zwyciężaj (ang. Divide & Conquer). Polega ona na podziale problemu na mniejsze problemy i wyznaczeniu rozwiązania z rozwiązań problemów mniejszych. W naszym przypadku zbiór rozdzielimy na dwa podzbiory - w jednym będą elementy mniejsze a w drugim elementy większe. W podzbiorze z elementami mniejszymi wyznaczymy element minimalny, a w podzbiorze z elementami większymi wyznaczymy element maksymalny.
Najpierw sprawdzimy, czy n jest liczbą parzystą. Jeśli nie, to na końcu zbioru dublujemy ostatni element. Parzysta liczba elementów jest nam potrzebna do zgrabnego podziału zbioru na dwie połówki. Zdublowanie ostatniego elementu zbioru nie wpłynie na wyznaczenie elementu minimalnego i maksymalnego.
Ze zbioru pobieramy kolejne dwa elementy i porównujemy ze sobą. Element mniejszy jest kandydatem na element minimalny. Element większy jest kandydatem na element maksymalny. Zatem po porównaniu dokonujemy dla mniejszego elementu testu na element minimalny, a dla większego dokonujemy testu na element maksymalny. Po przeglądnięciu wszystkich par elementów zbioru znajdujemy element minimalny i maksymalny.
Policzmy ilość niezbędnych porównań:
Ponieważ ze zbioru pobieramy po dwa elementy, to podziały na elementy mniejsze i większe wymagają n/2 porównań. Po wykonaniu każdego takiego porównania musimy sprawdzić, czy wyznaczone elementy są odpowiednio elementem minimalnym i maksymalnym. Czyli otrzymujemy n/2 porównań przy teście na element minimalny oraz n/2 porównań przy teście na element maksymalny. Zatem złożoność obliczeniowa naszego algorytmu wyrazi się wzorem:
T(n) =
3 n < 2n - 2 2 Otrzymany wynik jest dużo korzystniejszy niż wynik poprzedni. Zysk powstaje stąd, iż elementu minimalnego i maksymalnego poszukujemy w podzbiorach o liczebności dwa razy mniejszej niż zbiór wyjściowy.
Klasa złożoności obliczeniowej nie ulega zmianie i wynosi O(n).
Dane wejściowe
n - liczba elementów w zbiorze; n N, n > 0 d[ ] - zbiór, w którym poszukujemy elementu maksymalnego. Indeksy elementów rozpoczynają się od 1. Jeśli liczba elementów jest nieparzysta, to w zbiorze powinno być miejsce na jeden dodatkowy element. Dane wyjściowe
wmin - wartość wyznaczonego elementu minimalnego; pmin - pozycja elementu minimalnego; pmin N, 1 pmin n wmax - wartość wyznaczonego elementu maksymalnego; pmax - pozycja elementu maksymalnego; pmax N, 1 pmax n Zmienne pomocnicze
i - xxx i N, i {2,3,...,10}
krok 1: Jeśli n mod 2 0, to d[n + 1] d[n] krok 2: wmin d[1]; wmax d[1] krok 3: pmin 1; pmax 1 krok 4: i 1 krok 5: Dopóki i n: wykonuj kroki 6...12 krok 6: Jeśli d[i] < d[i + 1], to idź do kroku 7. Inaczej idź do kroku 10 krok 7: Jeśli d[i] < wmin, to wmin d[i]; pmin i krok 8: Jeśli d[i + 1] > wmax, to wmax d[i + 1]; pmax i + 1 krok 9: Idź do kroku 12 krok 10: Jeśli d[i + 1] < wmin, to wmin d[i + 1]; pmin i + 1 krok 11: Jeśli d[i] > wmax, to wmax d[i]; pmax i krok 12: i i + 2 i wróć do kroku 5 krok 13: Jeśli pmin > n, to pmin pmin - 1 krok 14: Jeśli pmax > n, to pmax pmax - 1 krok 15: Zakończ algorytm
Pierwszy test w algorytmie sprawdza, czy zbiór d[ ] składa się z parzystej liczby elementów (parzysta liczba elementów jest niezbędna do równego podziału na dwie połówki). Jeśli nie, to wymuszamy parzystą liczbę elementów przez zdublowanie ostatniego elementu zbioru.
Następnie inicjujemy zmienne dla elementu minimalnego i maksymalnego. Tymczasowo wpisujemy do nich wartość pierwszego elementu zbioru oraz pozycję pierwszego elementu.
Rozpoczynamy pętlę przeszukującą zbiór. W pętli porównujemy ze sobą kolejne pary elementów zbioru - i-ty z (i+1)-szym. Porównanie to pozwala nam określić, który z tych elementów jest kandydatem na element minimalny a który na maksymalny. W zależności od wyniku porównania idziemy jedną z dwóch ścieżek.
Ścieżką TAK podążamy, gdy element i-ty jest mniejszy od elementu (i+1)-szego. W takim przypadku sprawdzamy, czy i-ty element jest nowym elementem minimalnym, a (i+1)-szy jest nowym elementem maksymalnym. Jeśli któryś z tych warunków jest spełniony, to odpowiednio modyfikujemy zmienne dla elementu minimalnego i maksymalnego.. W przypadku ścieżki NIE mamy sytuację odwrotną. Element i-ty jest testowany na element maksymalny, a element (i+1)-szy na element minimalny (zobacz na uwagi końcowe).
Po wykonaniu testów zwiększamy indeks i o 2, czyli przechodzimy do kolejnej pary elementów w zbiorze d[ ]. Pętla jest wykonywana dotąd, aż wszystkie pary zostaną przetworzone. Na wyjściu w zmiennych wmin, pmin mamy wartość i pozycję elementu minimalnego, a w wmax i pmax wartość i pozycję elementu maksymalnego.
Na koniec musimy jeszcze sprawdzić, czy wyznaczona pozycja elementu minimalnego pmin nie leży poza zbiorem. Może się tak zdarzyć, gdy najmniejszy element znajduje się na ostatniej pozycji w zbiorze, a zbiór posiada nieparzystą liczbę elementów. W takiej sytuacji dublowaliśmy ostatni element. Zatem porównanie d[i] < d[i + 1] da wynik negatywny, ponieważ oba elementy są równe. Algorytm zaliczy jako wmin element na pozycji i + 1, a to jest poza ostatnim elementem wejściowego zbioru. Wystarczy jedynie zmniejszyć o 1 wartość pozycji pmin i wszystko będzie w porządku. Kończymy algorytm.
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 szuka elementu minimalnego i maksymalnego w 19-to elementowym zbiorze liczb pseudolosowych o wartościach z zakresu od 0 do 99. Znalezione elementy są odpowiednio zaznaczane.
Efekt uruchomienia programu |
---|
Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego |
// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------------------------
program searchminmax;
{$APPTYPE CONSOLE}
const
N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
var
d : array[1..N + 1] of cardinal;
i,wmin,pmin,wmax,pmax : cardinal;
begin
writeln('Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego');
writeln('------------------------------------------------------------');
writeln('(C)2006 mgr Jerzy Walaszek I LO w Tarnowie');
writeln;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego
randomize;
for i := 1 to N do d[i] := random(M + 1);
// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element
if N mod 2 <> 0 then d[N + 1] := d[N];
// Inicjujemy tymczasowe wartosci minimalne i maksymalne
wmin := d[1]; pmin := 1; wmax := d[1]; pmax := 1;
// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.
i := 1;
while i <= N do
begin
if d[i] < d[i + 1] then
begin
if d[i] < wmin then
begin
wmin := d[i]; pmin := i;
end;
if d[i + 1] > wmax then
begin
wmax := d[i + 1]; pmax := i + 1;
end;
end
else
begin
if d[i + 1] < wmin then
begin
wmin := d[i + 1]; pmin := i + 1;
end;
if d[i] > wmax then
begin
wmax := d[i]; pmax := i;
end;
end;
inc(i,2);
end;
if pmin = N + 1 then dec(pmin);
// Prezentujemy wyniki
for i := 1 to N do
if i = pmin then write('>',d[i]:2,'<')
else if i = pmax then write('<',d[i]:2,'>')
else write(' ',d[i]:2,' ');
writeln; writeln;
writeln('wmin = ',wmin:2,' na pozycji nr ',pmin:2);
writeln('wmax = ',wmax:2,' na pozycji nr ',pmax:2);
writeln;
// Gotowe
write('KONIEC. Nacisnij klawisz Enter...'); readln;
end.
// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------------------------
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
const int M = 99; // maksymalna wartość elementów
int main(void)
{
unsigned d[N + 2],i,wmin,pmin,wmax,pmax;
cout << "Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego\n"
"------------------------------------------------------------\n"
"(C)2006 mgr Jerzy Walaszek I LO w Tarnowie\n\n";
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego
srand((unsigned)time(NULL));
for(i = 1; i <= N; i++) d[i] = rand() % (M + 1);
// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element
if(N % 2) d[N + 1] = d[N];
// Inicjujemy tymczasowe wartosci minimalne i maksymalne
wmin = wmax = d[1]; pmin = pmax = 1;
// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.
for(i = 1; i <= N; i += 2)
if(d[i] < d[i + 1])
{
if(d[i] < wmin)
{
wmin = d[i]; pmin = i;
}
if(d[i + 1] > wmax)
{
wmax = d[i + 1]; pmax = i + 1;
}
}
else
{
if(d[i + 1] < wmin)
{
wmin = d[i + 1]; pmin = i + 1;
}
if(d[i] > wmax)
{
wmax = d[i]; pmax = i;
}
}
if(pmin == N + 1) pmin--;
// Prezentujemy wyniki
for(i = 1; i <= N; i++)
if(i == pmin) cout << ">" << setw(2) << d[i] << "<";
else if(i == pmax) cout << "<" << setw(2) << d[i] << ">";
else cout << " " << setw(2) << d[i] << " ";
cout << "\n\nwmin = " << setw(2) << wmin << " na pozycji nr " << setw(2) << pmin
<< "\nwmax = " << setw(2) << wmax << " na pozycji nr " << setw(2) << pmax
<< "\n\n";
// Gotowe
system("pause"); return 0;
}
' Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
'-------------------------------------------------------------
' (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
'-------------------------------------------------------------
Module Module1
Sub Main()
Const N = 19 ' liczba elementów w zbiorze - specjalnie nieparzysta!
Const M = 99 ' maksymalna wartość elementów
' Deklaracja zmiennych
Dim d(N + 1), i, wmin, pmin, wmax, pmax As UInteger
Console.WriteLine("Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego")
Console.WriteLine("------------------------------------------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie")
Console.WriteLine()
' Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
' elementu minimalnego i maksymalnego
Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next
' Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
' dublujemy ostatni element
If N \ 2 <> 0 Then d(N + 1) = d(N)
' Inicjujemy tymczasowe wartosci minimalne i maksymalne
wmin = d(1) : pmin = 1 : wmax = d(1) : pmax = 1
' Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
' poszukujemy elementu minimalnego. W podzbiorze elementów większych
' poszukujemy elementu maksymalnego.
For i = 1 To N Step 2
If d(i) < d(i + 1) Then
If d(i) < wmin Then
wmin = d(i) : pmin = i
End If
If d(i + 1) > wmax Then
wmax = d(i + 1) : pmax = i + 1
End If
Else
If d(i + 1) < wmin Then
wmin = d(i + 1) : pmin = i + 1
End If
If d(i) > wmax Then
wmax = d(i) : pmax = i
End If
End If
Next
If pmin = N + 1 Then pmin -= 1
' Prezentujemy wyniki
For i = 1 To N
If i = pmin Then
Console.Write(">{0,2}<", d(i))
ElseIf i = pmax Then
Console.Write("<{0,2}>", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next
Console.WriteLine()
Console.WriteLine()
Console.WriteLine("wmin = {0,2} na pozycji {1,2}", wmin, pmin)
Console.WriteLine("wmax = {0,2} na pozycji {1,2}", wmax, pmax)
Console.WriteLine()
' Gotowe
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()
End Sub
End Module
# -*- coding: cp1250 -*-
# Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
#-------------------------------------------------------------
# (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
#-------------------------------------------------------------
import random
N = 19 # liczba elementów w zbiorze - specjalnie nieparzysta!
M = 99 # maksymalna wartość elementów
d = []
print "Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego"
print "------------------------------------------------------------"
print "(C)2006 mgr Jerzy Walaszek I LO w Tarnowie"
# Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
# elementu minimalnego i maksymalnego
for i in range(N): d.append(random.randint(0, M))
# Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
# dublujemy ostatni element
if N % 2: d.append(d[N - 1])
# Inicjujemy tymczasowe wartości minimalne i maksymalne
wmin = wmax = d[0]; pmin = pmax = 0
# Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
# poszukujemy elementu minimalnego. W podzbiorze elementów większych
# poszukujemy elementu maksymalnego.
for i in range(0, N, 2):
if d[i] < d[i + 1]:
if d[i] < wmin: wmin, pmin = d[i], i
if d[i + 1] > wmax: wmax, pmax = d[i + 1], i + 1
else:
if d[i + 1] < wmin: wmin, pmin = d[i + 1], i + 1
if d[i] > wmax: wmax, pmax = d[i], i
if pmin == N: pmin -= 1
# Prezentujemy wyniki
for i in range(N):
if i == pmin: print ">%2d<" % d[i],
elif i == pmax: print "<%2d>" % d[i],
else: print " %2d " % d[i],
print "wmin = %2d na pozycji %2d" % (wmin, pmin)
print "wmax = %2d na pozycji %2d" % (wmax, pmax)
# Gotowe
raw_input("KONIEC. Naciśnij klawisz Enter...")
<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="frmmaxmin">
<h4 id="out_t" style="TEXT-ALIGN: center">
Jednoczesne wyszukiwanie elementu<br>
maksymalnego i minimalnego
</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>
// Jednoczesne wyszukiwanie elementu maksymalnego i minimalnego
//-------------------------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------------------------
function main()
{
var N = 19; // liczba elementów w zbiorze - specjalnie nieparzysta!
var M = 99; // maksymalna wartość elementów
var d = new Array(N + 2);
var i,wmin,pmin,wmax,pmax,t;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
// elementu minimalnego i maksymalnego
for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));
// Sprawdzamy, czy zbiór posiada parzystą ilość elementów. Jeśli nie, to
// dublujemy ostatni element
if(N % 2) d[N + 1] = d[N];
// Inicjujemy tymczasowe wartosci minimalne i maksymalne
wmin = wmax = d[1]; pmin = pmax = 1;
// Rozdzielamy zbiór na dwa podzbiory. W podzbiorze elementów mniejszych
// poszukujemy elementu minimalnego. W podzbiorze elementów większych
// poszukujemy elementu maksymalnego.
for(i = 1; i <= N; i += 2)
if(d[i] < d[i + 1])
{
if(d[i] < wmin)
{
wmin = d[i]; pmin = i;
}
if(d[i + 1] > wmax)
{
wmax = d[i + 1]; pmax = i + 1;
}
}
else
{
if(d[i + 1] < wmin)
{
wmin = d[i + 1]; pmin = i + 1;
}
if(d[i] > wmax)
{
wmax = d[i]; pmax = i;
}
}
if(pmin == N + 1) pmin--;
// Prezentujemy wyniki
t = "";
for(i = 1; i <= N; i++)
if(i == pmin) t += "<b><font color=blue>>" + d[i] + "<</font></b>";
else if(i == pmax) t += "<b><font color=red><" + d[i] + "></font></b>";
else t += " " + d[i] + " ";
t += "<br><br>wmin = " + wmin + " na pozycji nr " + pmin +
"<br>wmax = " + wmax + " na pozycji nr " + pmax
// 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