Login lub e-mail Hasło   

Algorytmy wyszukujące - jednoczesne max i min

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 danych znaleźć element maksymalny i minimalny. Jeśli podejdziemy do tego zadania w spos&o...
Wyświetlenia: 7.573 Zamieszczono 03/11/2006

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

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

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