Znajdowanie max i min

Zadanie znajdowania elementu maksymalnego lub minimalnego jest typowym zadaniem wyszukiwania, które rozwiązujemy przy pomocy algorytmu wyszukiwania liniowego. Za tymczasowy maksymalny (minimalny) element przyjmujemy pierwszy element zbioru. Następnie element tymczasowy porównujemy z kolejnymi elementami. Jeśli któryś z porównywanych elementów jest większy (mniejszy) od elementu tymczasowego, to za nowy tymczasowy element maksymalny (minimalny) przyjmujemy porównywany element zbioru. Gdy cały zbiór zostanie przeglądnięty, w elemencie tymczasowym otrzymamy element maksymalny (minimalny) w zbiorze.

Poniżej podajemy algorytm wyszukiwania max. Wyszukiwanie min wykonuje się identycznie, zmianie ulega tylko warunek porównujący element tymczasowy z elementem zbioru w kroku K03.

 

Algorytm wyszukiwania elementu maksymalnego w zbiorze

Wejście
n      liczba elementów w tablicy Z[ ], n N
Z[ ]  – tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.
Wyjście:

Wartość największego elementu zbioru.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i   C
maxZ  – tymczasowy element maksymalny
Lista kroków:
K01: maxZZ[0] ; za tymczasowy element maksymalny bierzemy pierwszy element
K02: Dla i = 1,2,...,n-1 wykonuj K03 ; przeglądamy następne elementy zbioru
K03:     Jeśli Z[i] > maxZ, to maxZZ[i] ; jeśli natrafimy na większy od maxZ, to zapamiętujemy go w maxZ
K04: Zakończ zwracając maxZ  

 

Czasami zależy nam nie na wartości elementu maksymalnego (minimalnego), lecz na jego pozycji w zbiorze. W tym przypadku musimy, oprócz wartości samego elementu maksymalnego (minimalnego), zapamiętywać jego pozycję, którą na końcu zwracamy jako wynik pracy algorytmu.

 

Algorytm wyszukiwania pozycji elementu maksymalnego w zbiorze

Wejście
n      liczba elementów w tablicy Z[ ], n N
Z[ ]  – tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.
Wyjście:

Pozycja (indeks) elementu maksymalnego. W maxZ jest wartość elementu maksymalnego.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i   C
maxZ  – tymczasowy element maksymalny
maxp  – pozycja tymczasowego elementu maksymalnego
Lista kroków:
K01: maxZZ[0] ; za tymczasowy element maksymalny bierzemy pierwszy element
K02: maxp ← 0 ; zapamiętujemy jego pozycję
K03: Dla i = 1,2,...,n-1 wykonuj K04...K06 ; przeglądamy następne elementy zbioru
K04:     Jeśli Z[i] > maxZ, to idź do K05
    inaczej kontynuuj następny obieg pętli K03
; sprawdzamy, czy trafiliśmy na element większy od maxZ
K05:     maxZ ← Z[i]    ; jeśli tak, to zapamiętujemy wartość elementu w maxZ
K06:     maxp ← i ; oraz jego pozycję w maxp
K07: Zakończ zwracając maxp ; zwracamy zapamiętaną pozycję

 

Jednoczesne wyszukiwanie max i min

Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:

Wejście
n      liczba elementów w tablicy Z[ ], n N
Z[ ]  – tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.
Wyjście:

Wartość najmniejszego i największego elementu w tablicy Z[ ].

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i   C
maxZ  – tymczasowy element maksymalny
minZ  – tymczasowy element minimalny

 

Numer Operacja Liczba wykonań
1 minZZ[0] 1
2 maxZZ[0] 1
3 i ← 1 1
4 Jeśli i = n, to idź do 9 n
5 Jeśli Z[i] < minZ, to minZZ[i] n - 1
6 Jeśli Z[i] > maxZ, to maxZZ[i] n - 1
7 ii + 1 n - 1
8 Idź do 4 n - 1
9 Pisz minZ, maxZ 1
10 Zakończ 1

 

Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z minZ oraz z maxZ. Tutaj tkwi nieefektywność. Obie operacje nr 5 i 6 są wykonywane po n - 1 razy, co daje w sumie 2n - 2 porównania w całym zbiorze.

Wyobraźmy sobie, iż ze zbioru bierzemy parę 2 elementów i porównujemy je ze sobą. Element większy nie może być minimalnym, zatem nie musimy go już porównywać z minZ. Wystarczy porównanie z maxZ. To samo dotyczy elementu mniejszego – porównujemy go tylko z minZ. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z minZ i maxZ). Teraz mamy:

 

Jedno porównanie dwóch elementów, które rozdzieli je na element mniejszy i element większy.
Element mniejszy porównujemy z minZ.
Element większy porównujemy z maxZ.

 

Daje to 3 porównania zamiast 4. Ponieważ ze zbioru pobieramy po dwa kolejne elementy, to ich liczba musi być parzysta. Jeśli zbiór ma nieparzystą liczbę elementów, to po prostu dublujemy ostatni element i dostaniemy parzystą liczbę elementów.

Porównanie pary elementów dzieli zbiór na dwa podzbiory – zbiór elementów większych i mniejszych. W podzbiorze elementów większych szukamy elementu maksymalnego, a w podzbiorze elementów mniejszych szukamy minimalnego. Ponieważ ich liczebność jest o połowę mniejsza od liczebności zbioru wejściowego, to wykonamy mniej operacji porównań.

Metoda rozwiązywania problemów przez podział na mniejsze części w informatyce nosi nazwę Dziel i Zwyciężaj (ang. Divide and Conquer). Dzięki niej często udaje się zmniejszyć złożoność obliczeniową wielu algorytmów.

 

Algorytm jednoczesnego wyszukiwania max i min w zbiorze

Wejście
n      liczba elementów w tablicy Z[ ], n N
Z[ ]  – tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1. Tablica musi umożliwiać dodanie elementu, jeśli n jest nieparzyste.
Wyjście:

Element minimalny i maksymalny w tablicy Z[ ]

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i C
maxZ  – tymczasowy element maksymalny
maxp  – pozycja tymczasowego elementu maksymalnego
Lista kroków:
K01: Jeśli n mod 2 = 1, Z[n] ← Z[n-1] ; jeśli nieparzysta liczba elementów, dublujemy ostatni
K02: minZ ← największa liczba całkowita ; inicjujemy minZ i maxZ
K03: maxZ ← najmniejsza liczba całkowita  
K04: i ← 0  
K05: Dopóki i < n wykonuj K06...K12 ; wybieramy pary kolejnych elementów
K06:     Jeśli Z[i] > Z[i+1], to idź do K10 ; rozdzielamy je na element mniejszy i większy
K07:     Jeśli Z[i] < minZ, to minZZ[i] ; Z[i] - mniejszy, Z[i+1] - większy
K08:     Jeśli Z[i+1] > maxZ, to maxZZ[i+1]  
K09:     Idź do K12  
K10:     Jeśli Z[i] > maxZ, to maxZZ[i] ; Z[i] - większy, Z[i+1] - mniejszy
K11:     Jeśli Z[i+1] < minZ, to minZZ[i+1]  
K12:     ii + 2 ; przechodzimy do następnej pary elementów
K13: Pisz minZ, maxZ ; wyprowadzamy wyniki
K14: Zakończ  

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.