Algorytmy wyszukujące - jednoczesne max i min

26437fb1a826ab8529279ce8a03174c7.gif

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).

8f649dcab2d91e5db4ec9cc501e83133.gif

Dane wejściowe

n - liczba elementów w zbiorze;  n 066711e53c489d1cb00531a110803f75.gif 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 066711e53c489d1cb00531a110803f75.gif N,   1 0c7294ac96706b86953864dcf5f43c44.gif pmin 0c7294ac96706b86953864dcf5f43c44.gif n
wmax - wartość wyznaczonego elementu maksymalnego;
pmax - pozycja elementu maksymalnego;   pmax 066711e53c489d1cb00531a110803f75.gif N,   1 0c7294ac96706b86953864dcf5f43c44.gif pmax 0c7294ac96706b86953864dcf5f43c44.gif n

Zmienne pomocnicze

i - xxx i 066711e53c489d1cb00531a110803f75.gif N,   i 066711e53c489d1cb00531a110803f75.gif {2,3,...,10}
abd892daa022d4686052f660aaae76a0.gif
krok 1: Jeśli n mod 2 772ba1c2b2b301992e7ecc9d36c4e6f5.gif 0, to d[n + 1] e71e6127157d188d2130b7ab6c0f9377.gif d[n]
krok 2: wmin e71e6127157d188d2130b7ab6c0f9377.gif d[1];  wmax e71e6127157d188d2130b7ab6c0f9377.gif d[1]
krok 3: pmin e71e6127157d188d2130b7ab6c0f9377.gif 1;  pmax e71e6127157d188d2130b7ab6c0f9377.gif 1
krok 4: i e71e6127157d188d2130b7ab6c0f9377.gif 1
krok 5: Dopóki i 0c7294ac96706b86953864dcf5f43c44.gif 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 e71e6127157d188d2130b7ab6c0f9377.gif d[i];   pmin e71e6127157d188d2130b7ab6c0f9377.gif i
krok 8:     Jeśli d[i + 1] > wmax, to wmax e71e6127157d188d2130b7ab6c0f9377.gif d[i + 1];   pmax e71e6127157d188d2130b7ab6c0f9377.gif i + 1
krok 9:     Idź do kroku 12
krok 10:     Jeśli d[i + 1] < wmin, to wmin e71e6127157d188d2130b7ab6c0f9377.gif d[i + 1];   pmin e71e6127157d188d2130b7ab6c0f9377.gif i + 1
krok 11:     Jeśli d[i] > wmax, to wmax e71e6127157d188d2130b7ab6c0f9377.gif d[i];   pmax e71e6127157d188d2130b7ab6c0f9377.gif i
krok 12:     i e71e6127157d188d2130b7ab6c0f9377.gif i + 2 i wróć do kroku 5
krok 13: Jeśli pmin > n, to pmin e71e6127157d188d2130b7ab6c0f9377.gif pmin - 1
krok 14: Jeśli pmax > n, to pmax e71e6127157d188d2130b7ab6c0f9377.gif pmax - 1
krok 15: Zakończ algorytm
0dede3c2a9eee5a65cf45a4c39e95f44.gif

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.

71f8dc14ae37334dae51d657c8788dff.gif
41d330f7e34bbe5786f1465f6a3b58c6.gif    
   
   

3db766c8f9c40eabb7b2685bfc2ed65e.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 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
------------------------------------------------------------
(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie

48 68 63 62 78 <83> 32 32 61 81 23 33 60 > 5< 7 35 18 61 78

wmin = 5 na pozycji 14
wmax = 83 na pozycji 6

KONIEC. Naciśnij dowolny klawisz...

fe1c63523832d4c0935ed14361286ff6.gif
// 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.
3160aa4a6525eb1da714491ee6ba9c61.gif
// 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;
}
00734983fe78c2768a9ed4b167c8d7a2.gif
' 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
9c53052d7fc25f0294072ed21f66bfce.gif
# -*- 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"
print

# 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
print

print "wmin = %2d na pozycji %2d" % (wmin, pmin)
print "wmax = %2d na pozycji %2d" % (wmax, pmax)
print

# Gotowe

raw_input("KONIEC. Naciśnij klawisz Enter...")
9107b5f3d9bfad678acf3505383c652c.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="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>&gt;" + d[i] + "&lt;</font></b>";
else if(i == pmax) t += "<b><font color=red>&lt;" + d[i] + "&gt;</font></b>";
else t += " " + d[i] + "&nbsp;";
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