Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
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).
| n | - | liczba elementów |
| T[ ] | - | tablica n elementowa zawierająca przeszukiwane elementy zbioru |
vmax - wartość największego elementu w T[ ].
| 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
Zaprojektuj algorytm wyszukiwania elementu najmniejszego w zbiorze.
Zaprojektuj algorytm wyszukiwania pozycji największego elementu zbioru.
Zaprojektuj algorytm jednoczesnego wyszukiwania elementu największego i najmniejszego.
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.
| 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. |
vmin - wartość najmniejszego elementu w T[ ].
vmax - wartość największego elementu w T[ ].
| 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
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe