Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
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 T, n N |
T | – | tablica zawierająca elementy do zliczania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1. |
tmax – wartość elementu maksymalnego.
i | – | przebiega przez kolejne indeksy elementów T. i C |
tmax | – | tymczasowy element maksymalny |
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.
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. |
pmax – pozycja (indeks)
elementu maksymalnego
tmax – wartość elementu maksymalnego.
i | – | przebiega przez kolejne indeksy elementów T. i C |
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 |
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
Napisz programy, które w tym zbiorze znajdą:
Jeśli do wyszukiwania elementu max i min zastosujemy standardowy algorytm, to otrzymamy:
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. |
tmax – wartość elementu maksymalnego.
tmin – wartość elementu minimalnego.
i | – | przebiega przez kolejne indeksy elementów T. i C |
Numer | Operacja | Liczba wykonań |
K01 | tmin ← T[0] | 1 |
K02 | tmax ← T[0] | 1 |
K03 | i ← 1 | 1 |
K04 | Jeśli i = n, to idź do K09 | n |
K05 | Jeśli T[i] < tmin, to tmin ← T[i] | n - 1 |
K06 | Jeśli T[i] > tmax, to tmax ← T[i] | n - 1 |
K07 | i ← i + 1 | n - 1 |
K08 | Idź do K04 | n - 1 |
K09 | 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 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.
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. |
tmax – wartość elementu maksymalnego.
tmin – wartość elementu minimalnego.
i | – | przebiega przez kolejne indeksy elementów Z. i C |
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 |
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