Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
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.
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. |
Wartość największego elementu zbioru.
i | – | przebiega przez kolejne indeksy elementów Z[ ]. i C |
maxZ | – | tymczasowy element maksymalny |
K01: | maxZ ← Z[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 maxZ ← Z[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.
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. |
Pozycja (indeks) elementu maksymalnego. W maxZ jest wartość elementu maksymalnego.
i | – | przebiega przez kolejne indeksy elementów Z[ ]. i C |
maxZ | – | tymczasowy element maksymalny |
maxp | – | pozycja tymczasowego elementu maksymalnego |
K01: | maxZ ← Z[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ę |
Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:
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. |
Wartość najmniejszego i największego elementu w tablicy Z[ ].
i | – | przebiega przez kolejne indeksy elementów Z[ ]. i C |
maxZ | – | tymczasowy element maksymalny |
minZ | – | tymczasowy element minimalny |
Numer | Operacja | Liczba wykonań |
1 | minZ ← Z[0] | 1 |
2 | maxZ ← Z[0] | 1 |
3 | i ← 1 | 1 |
4 | Jeśli i = n, to idź do 9 | n |
5 | Jeśli Z[i] < minZ, to minZ ← Z[i] | n - 1 |
6 | Jeśli Z[i] > maxZ, to maxZ ← Z[i] | n - 1 |
7 | i ← i + 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
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.
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. |
Element minimalny i maksymalny w tablicy Z[ ]
i | – | przebiega przez kolejne indeksy elementów Z[ ]. i C |
maxZ | – | tymczasowy element maksymalny |
maxp | – | pozycja tymczasowego elementu maksymalnego |
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 minZ ← Z[i] | ; Z[i] - mniejszy, Z[i+1] - większy |
K08: | Jeśli Z[i+1] > maxZ, to maxZ ← Z[i+1] | |
K09: | Idź do K12 | |
K10: | Jeśli Z[i] > maxZ, to maxZ ← Z[i] | ; Z[i] - większy, Z[i+1] - mniejszy |
K11: | Jeśli Z[i+1] < minZ, to minZ ← Z[i+1] | |
K12: | i ← i + 2 | ; przechodzimy do następnej pary elementów |
K13: | Pisz minZ, maxZ | ; wyprowadzamy wyniki |
K14: | Zakończ |
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