Wyszukiwanie max i min

Zadanie wyszukania w zbiorze wartości największej (ang. maximum value) lub najmniejszej (ang. minimum value) jest jednym z częstszych zadań, z którymi spotyka się programista. Jednocześnie jest to typowe zadanie wyszukiwania, w którym jednakże nie poszukujemy wartości v (gdyż jej nie znamy), lecz elementu zbioru o określonej własności (o największej/najmniejszej wartości ze wszystkich elementów w zbiorze). Wynikiem wyszukiwania jest najczęściej wartość elementu, lecz może to również być pozycja największego elementu w zbiorze - wszystko zależy od planowanego zastosowania otrzymanego wyniku.

 Znajdowanie największego/najmniejszego elementu wykonujemy wg następującego schematu:

Rozpoczynamy przyjmując za największy/najmniejszy element pierwszy element zbioru. Nazwijmy go roboczo vmax/vmin. Teraz porównujemy wszystkie następne elementy zbioru z vmax/vmin. Jeśli porównywany element jest większy/mniejszy od vmax/vmin, to zapamiętujemy go w vmax/vmin. Dzięki temu vmax/vmin zawiera zawsze wartość największego/najmniejszego  elementu z dotychczas przetworzonych elementów zbioru. Gdy przetworzymy już wszystkie elementy w zbiorze, vmax/vmin będzie zawierać element największy/najmniejszy w całym zbiorze.

Tak skonstruowany algorytm posiada klasę złożoności obliczeniowej O(n).

 

Algorytm wyszukiwania elementu największego w zbiorze

Wejście:
n  -  liczba elementów
T[ ]  - tablica n elementowa zawierająca przeszukiwane elementy zbioru
Wyjście:

vmax - wartość największego elementu w T[ ].

Lista kroków:
K01: vmax ← T[0] ; przyjmujemy roboczy największy element
K02: Dla i = 1,2,...,n-1: wykonuj:
    Jeśli
T[i] > vmax, to vmax ← T[i]
; jeśli bieżący element jest większy od vmax, to
; zapamiętujemy go w vmax
K03: Pisz vmax  
K04: Zakończ  

Program:

Ćwiczenie na lekcji

 

Ćwiczenia

  1. Zaprojektuj algorytm wyszukiwania elementu najmniejszego w zbiorze.

  2. Zaprojektuj algorytm wyszukiwania pozycji największego elementu zbioru.

  3. Zaprojektuj algorytm jednoczesnego wyszukiwania elementu największego i najmniejszego.

 

Jednoczesne wyszukiwanie max i min

W ćwiczeniu 3 tworzyliśmy algorytm, który jednocześnie wyszukiwał element maksymalny i minimalny zbioru. Standardowe podejście wymaga dla n elementów wykonania 2n-2 porównań elementów zbioru. Algorytm możemy przyspieszyć następująco:

Tworzymy dwa puste podzbiory;
Tmin - zbiór elementów mniejszych
Tmax - zbiór elementów większych

Ze zbioru T wybieramy kolejne pary sąsiednich elementów. Elementy w parze porównujemy ze sobą. Element mniejszy umieszczamy w Tmin, a element większy umieszczamy w Tmax. Po rozdzieleniu całego zbioru T na Tmin i Tmax w zbiorze Tmin poszukujemy elementu minimalnego, a w zbiorze Tmax poszukujemy elementu maksymalnego. Ma to sens, ponieważ element mniejszy nie może być elementem maksymalnym w zbiorze i na odwrót, element większy nie może być elementem minimalnym.

Policzmy liczbę porównań elementów w tym algorytmie:

Podział zbioru T na Tmin i Tmax wymaga n/2 porównań.

Ponieważ zbiory Tmin i Tmax są o połowę mniej liczne od zbioru T, to:
wyszukanie vmin w Tmin - n/2-1 porównań
wyszukanie vmax w Tmax - n/2-1 porównań

Razem mamy 3n/2-2 porównań, co jest wynikiem mniejszym od poprzednio otrzymanego 2n-2.

Algorytm posiada klasę złożoności obliczeniowej O(n), jednakże jest bardziej efektywny od dwóch algorytmów wyszukiwania min i max zastosowanych oddzielnie dla całego zbioru.

Zatem nowy algorytm będzie pracował szybciej. Zasada, wg której on działa nosi nazwę zasady dziel i zwyciężaj (ang. divide and conquer). Polega ona na podzieleniu problemu na odpowiednią liczbę problemów mniejszych i rozwiązaniu ich, a następnie utworzeniu rozwiązania problemu głównego z rozwiązań cząstkowych.

W implementacji algorytmu nie musimy fizycznie tworzyć zbiorów Tmin oraz Tmax. Możemy bezpośrednio działać na ich elementach. Tak właśnie postąpimy.

 

Algorytm jednoczesnego wyszukiwania elementu min i max

Wejście:
n  -  liczba elementów
T[ ]  - tablica n elementowa zawierająca przeszukiwane elementy zbioru. Jeśli n jest nieparzyste, to tablica powinna być n+1 elementowa.
Wyjście:

vmin - wartość najmniejszego elementu w T[ ].

vmax - wartość największego elementu w T[ ].

Lista kroków:
K01: Jeśli n nieparzyste, to T[n] ←T[n - 1];  n n + 1 ; zapewniamy podział zbioru na dwa równe podzbiory
K02: Jeśli T[0] < T[1], to vmin ← T[0];   vmax ← T[1]
inaczej                  vmin ← T[1];   vmax ← T[0]
; inicjujemy robocze vmin i vmax
K03: Dla i = 2,4,..n - 2; wykonuj K04...K09 ; dzielimy T na dwa podzbiory
K04:     Jeśli T[i] < T[i+1], to idź do K08  
K05:     Jeśli T[i] > vmax, to vmax ← T[i] ; T[i] należy do Tmax, T[i+1] należy do Tmin
K06:     Jeśli T[i+1] < vmin, to vmin ← T[i+1]  
K07:     Kontynuuj pętlę K03  
K08:     Jeśli T[i] < vmin, to vmin ← T[i] ; T[i] należy do Tmin, T[i+1] należy do Tmax
K09:     Jeśli T[i+1] > vmax, to vmax ← T[i+1]  
K10: Pisz vmin, vmax  
K11: Zakończ  

Program:

Ćwiczenie na lekcji

 



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.