Znajdowanie min i max

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 T, n  N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

tmax  – wartość elementu maksymalnego.

Zmienne pomocnicze

i	–	przebiega przez kolejne indeksy elementów T. i    C
tmax	–	tymczasowy element maksymalny

Lista kroków:

K01:	tmax  ← T[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 T[i] > tmax, to tmax  ← T[i]	; jeśli natrafimy na większy od tmax, to zapamiętujemy go w tmax
K04:	Zakończ

Czasami zależy nam nie tylko na wartości elementu maksymalnego (minimalnego), lecz również 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 T, n  N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

pmax  – pozycja (indeks) elementu maksymalnego
tmax  – wartość elementu maksymalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów T. i    C

Lista kroków:

K01:	tmax  ← T[0]	; za tymczasowy element maksymalny bierzemy pierwszy element
K02:	pmax  ← 0	; zapamiętujemy jego pozycję
K03:	Dla i  = 1,2,...,n-1 wykonuj K04...K06	; przeglądamy następne elementy zbioru
K04:	Jeśli T[i] ≤ tmax,  to następny obieg pętli K03	; sprawdzamy, czy trafiliśmy na element większy od tmax
K05:	tmax  ← T[i]	; jeśli tak, to zapamiętujemy wartość elementu w tmax
K06:	pmax  ← i	; oraz jego pozycję w pmax
K07:	Zakończ

 

Ćwiczenia

390
-2250 -7552 -4064   410  5962  6322  7079  4722  -608  9078 -2298 -5421  3009
-8412  4516  1466   330  9176  6659  5201 -8953 -3400 -8677  9568  5363   518
 8663  -522 -6287 -8246  3441 -7882 -1176  6717 -2035 -9981  6657 -7370  2711
 5098  8257  2966 -4485  9298 -3258  4530  3240  9349 -8542  5988 -2587  5116
 4152  2928  7919  9516  8569  -553  1624  8562 -1058  6431  8288  3808   932
 -450 -2383  -410  9418 -2039 -4996  3680  3914 -9441  4438  1250  3257  3988
-3247  4323  1407 -1633  1530  2605  6006  4131 -1323  7233 -2301  3358 -8613
-9685 -9834  3892 -8592  2506   -62 -8679  5573  -485 -3429  1601  -399 -5717
 9491  5352  8558  8281  2515  7425 -8299 -7282  1306 -9728 -2759   317   472
 2119 -1402  2296  3688 -1519  9366 -1544  5264 -6624  2423  9450  2233  9575
 2079 -2533 -6483  -840  -213 -6685 -3501 -4757 -2309  5522  4780  8627 -4850
 3451  8971    65  1277  -125  7255  7893  4792   712  2465   -86  3779 -8782
 6885  2141  5839  8475  9825 -9279  5881  9022  1495  4260  -732  5313 -5789
  831   149  8770  3387  1089 -3726   804  8906  6041  1627  1879 -3637 -2298
 9253  5545 -1658  2687  8569   272  -947  6529  2735 -1230 -3052  9405  8682
 7035  -718  1310  3858  4636  5818  4348  1045  5572  7513  5698  -868  6113
 5070  2592 -7988  5906   875  9648 -1149 -4780   623  1769  8944  9034 -3905
 2598 -7089  7657 -2712  3604  4522 -9430  7030 -1730  8719  1005  8434 -4807
-8783  7981 -8898 -2480  8193 -5624   880 -4883  2953 -9492 -3056  1548  8109
-9247 -7469  6528  6912  7129  9876  1026   -25  6744  3990  2302  7633 -2333
 9658  6652 -5038  5035  4161  2704     3  1495  2241  -991 -2726 -2348   904
 5114  3465 -6788  3794   306  6424  1287  9515  7964  4673  1460   868 -2257
  720  8534  4117 -2189 -3720  5344  7927 -9552   276 -1137  9023 -2153 -6462
-2182  1019  5102  7840  3354  7469  1245  1060 -9478 -3511  3610 -1923  5790
 8174  9781  1228  6836 -7386  6691 -5951   892 -1346  7915   -11  9590  5669
 8274 -4469 -1712  5734 -8472 -9082 -1299  1668 -5713  3466  7029  4056 -2352
 7282 -2081  7628 -5604  9461 -1409 -2667 -2685 -5928  8112  6195 -9097   977
-5728  -887  -738  -446  5375  9788 -1542  8177  8934  9228  1817  8040  1032
-2349 -4163   911 -5958   833  4553  6636  2626 -7116  4688  7382  9377  5272
 1374 -8035 -1952 -8701 -1341 -4293  8957  -146 -3260 -5738  6643 -2509  8416

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 T, n  N
T	–	tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n  - 1.

Wyjście:

tmax  – wartość elementu maksymalnego.
tmin  – wartość elementu minimalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów T. i    C

Zastanówmy się, czy można uzyskać lepszy wynik. Algorytm porównuje każdy element zbioru z tmin  oraz z tmax. Tutaj tkwi nieefektywność. Obie operacje z kroków K05 i K06 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 tmin. Wystarczy porównanie z tmax. To samo dotyczy elementu mniejszego – porównujemy go tylko z tmin. Otrzymujemy zysk – poprzednio dwa elementy wymagały wykonania 4 porównań (każdy z tmin  i tmax). 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 tmin.
Element większy porównujemy z tmax.

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 T, n  N
T	–	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:

tmax  – wartość elementu maksymalnego.
tmin  – wartość elementu minimalnego.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów Z. i  C

Lista kroków:

K01:	Jeśli n  mod 2 = 1, T[n] ← T[n-1]	; jeśli nieparzysta liczba elementów, dublujemy ostatni
K02:	tmin  ← największa liczba całkowita	; inicjujemy tmin i tmax
K03:	tmax  ← najmniejsza liczba całkowita
K04:	i  ← 0
K05:	Dopóki i  < n  wykonuj K06...K12	; wybieramy pary kolejnych elementów
K06:	Jeśli T[i] > T[i+1], to idź do K10	; rozdzielamy je na element mniejszy i większy
K07:	Jeśli T[i] < tmin, to tmin  ← T[i]	; T[i] - mniejszy, T[i+1] - większy
K08:	Jeśli T[i+1] > tmax, to tmax  ← T[i+1]
K09:	Idź do K12
K10:	Jeśli T[i] > tmax, to tmax  ← T[i]	; T[i] - większy, T[i+1] - mniejszy
K11:	Jeśli T[i+1] < tmin, to tmin  ← T[i+1]
K12:	i  ← i  + 2	; przechodzimy do następnej pary elementów
K13:	Zakończ

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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