Informatyka dla klas II - Wyszukiwanie najczęstszego elementu

Rozwiązanie nr 1

Problem wyszukiwania najczęstszej wartości (ang. searching for the most frequent value), czyli tzw. dominanty zbioru, możemy rozwiązać na kilka różnych sposobów. Pierwszym, najprostszym podejściem jest metoda bezpośrednia – naiwna:

 

Przeglądamy kolejne elementy zbioru i zliczamy liczbę wystąpień ich wartości w zbiorze. Można to robić tak – zapamiętujemy i-ty element i ustawiamy licznik wystąpień na 0. Następnie przeglądamy cały zbiór i, jeśli trafimy na element o takiej samej wartości, to licznik zwiększamy o 1. Po wykonaniu tej operacji porównujemy zawartość licznika z tymczasową maksymalną liczbą wystąpień (na początku algorytmu jest ona ustawiana na 0). Jeśli stan licznika jest większy, to zapamiętujemy go w tymczasowej maksymalnej liczbie wystąpień oraz zapamiętujemy wyszukiwaną wartość elementu. Gdy przeglądniemy w ten sposób i zliczymy wystąpienia wartości wszystkich elementów w zbiorze T, to otrzymamy element powtarzający się najczęściej oraz ilość tych powtórzeń.

Klasa złożoności obliczeniowej tak zdefiniowanego algorytmu jest równa O(n2). Jeśli elementów jest niewiele (do około 5000) i szybkość działania nie gra istotnej roli, to rozwiązanie naiwne jest do przyjęcia – tak właśnie było w przypadku zadania maturalnego.

 

Algorytm wygląda następująco:

 

Algorytm znajdowania najczęstszej wartości – wersja nr 1

Wejście
n      liczba elementów w tablicy T, n N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..
Wyjście:

Element występujący najczęściej w T oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm zwraca pierwszy z nich, który został napotkany w zbiorze.

Zmienne pomocnicze
i, j  –  przebiega przez kolejne indeksy elementów T. i,j C
L  – licznik wystąpień wartości elementu, L C
W  – wartość elementu, której liczbę wystąpień w T zliczamy.
maxW  – najczęstsza wartość elementów tablicy T
maxL  – liczba wystąpień wartości najczęstszej. maxL C
Lista kroków:
K01: maxL ← 0 ; zerujemy maksymalną liczbę wystąpień
K02: Dla i = 0,1,...,n - 1 wykonuj K03...K09 ; przeglądamy kolejne elementy tablicy T
K03:     W T[i] ; zapamiętujemy poszukiwaną wartość elementu
K04:     L ← 0 ; zerujemy jej licznik wystąpień
K05:     Dla j = 0,1,...,n - 1 wykonuj K06 ; zliczamy wystąpienia W
K06:         Jeśli T[j] = W, to LL + 1  
K07:     Jeśli LmaxL, to następny obieg pętli K2 ; sprawdzamy, czy W jest tymczasowo najczęstsze
K08:     maxLL ; jeśli tak, zapamiętujemy liczbę wystąpień
K09:     maxWW ; oraz wartość W
K10: Pisz maxW, maxL ; wypisujemy wyniki
K11: Zakończ  

 

Przykładowe dane do ćwiczeń:

400
21 84 16 62 83 81 6 92 96 85 18 72 70 96 8 37 23 91 74 99
87 14 33 20 58 25 42 55 41 3 91 23 38 98 42 91 51 35 31 39
65 17 46 5 89 85 39 5 60 85 30 36 60 80 73 9 6 90 55 51
5 84 25 75 16 71 39 85 70 6 6 72 30 93 55 93 67 6 35 35
48 18 65 25 50 11 17 90 15 30 84 82 64 5 50 74 47 11 10 92
79 0 6 1 75 79 65 11 33 22 86 24 61 96 12 46 29 82 23 62
35 36 39 26 59 46 97 57 29 58 69 86 27 28 17 81 55 38 26 45
76 39 16 71 78 29 49 42 6 38 24 25 45 52 89 49 52 36 92 79
49 26 57 86 11 17 67 93 96 29 96 16 79 36 70 19 11 20 60 46
43 85 25 90 11 96 1 92 80 20 60 1 13 30 72 80 85 47 87 67
29 90 20 98 47 6 95 60 19 77 90 22 13 52 23 50 54 45 29 50
4 21 60 56 75 59 94 5 88 85 15 49 5 77 64 62 71 82 32 42
59 35 8 45 44 52 71 7 12 79 58 29 9 7 90 85 87 68 65 38
32 0 55 12 56 76 97 58 24 91 97 62 49 34 49 96 6 18 44 15
50 3 32 13 67 16 38 69 89 66 73 84 82 57 68 65 89 19 49 33
34 94 13 27 19 5 49 59 82 21 25 38 49 94 85 45 48 63 53 2
1 70 37 13 89 51 44 20 24 46 74 89 2 11 87 28 83 30 23 81
64 27 15 81 95 93 71 29 47 45 17 64 90 77 1 73 61 26 79 47
91 82 17 88 26 22 57 63 12 14 43 74 31 40 50 28 36 61 77 77
15 19 41 71 23 24 3 33 32 65 30 97 85 38 62 87 82 65 53 24

 

Rozwiązanie nr 2

Podany powyżej algorytm jest bardzo prymitywny i wykonuje wiele niepotrzebnych działań. Postarajmy się je wyeliminować.

  1. Ze zbioru bierzemy KAŻDY element T[i] i zliczamy wystąpienia jego wartości W w CAŁYM zbiorze T. W ten sposób najczęstsza wartość maxW zostanie zliczona maxL2 razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element W zbioru zliczamy tylko wtedy, gdy jest on różny od maxW. Wynika z tego, iż na początku pracy algorytmu do maxW musimy wpisać wartość różną od T[0] (dlaczego?).
  2. Każdy element T[i] zliczamy w całym zbiorze. Tymczasem, jeśli wartość i-tego elementu wystąpiła wcześniej w zbiorze, to jest już zliczona. Jeśli nie wystąpiła wcześniej, to nie ma sensu jej tam szukać, nieprawdaż? W obu przypadkach wystarczy, jeśli zliczanie rozpoczniemy od pozycji i + 1 do końca zbioru. Elementy zliczone po prostu zliczymy ponownie, lecz w mniejszym zakresie. Elementy nowe zliczymy poprawnie, od miejsca ich pierwszego wystąpienia.
  3. Jeśli w trakcie działania algorytmu w maxL mamy chwilową maksymalną liczbę wystąpień pewnej wartości maxW, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n - maxL. Jeśli nowy element występuje na tej lub dalszej pozycji w zbiorze T, to liczba wystąpień jego wartości nie będzie już większa od maxL, gdyż braknie elementów.

Algorytm znajdowania najczęstszej wartości – wersja nr 2

Wejście
n     liczba elementów w tablicy T, n N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..
Wyjście:

Element występujący najczęściej w T oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm zwraca pierwszy z nich, który został napotkany w zbiorze.

Zmienne pomocnicze
i, j  –  przebiega przez kolejne indeksy elementów T. i,j C
L  – licznik wystąpień wartości elementu, L C
W  – wartość elementu, której liczbę wystąpień w T zliczamy.
maxW  – najczęstsza wartość elementów tablicy T
maxL  – liczba wystąpień wartości najczęstszej. maxL C
Lista kroków:
K01: maxL ← 0 ; licznik wystąpień najczęstszej wartości
K02: maxW T[0] - 1 ; najczęstsza wartość - musi być różna od T[0]!
K03: i ← 0 ; rozpoczynamy zliczanie wartości elementów
K04: Dopóki i < n - maxL, wykonuj K05...K13 ; zliczamy do n-maxL
K05:     W T[i] ; zapamiętujemy wartość bieżącego elementu
K06:     Jeśli W = maxW, to idź do K13 ; jeśli jest równa maxW, to pomijamy element T[i]
K07:     L ← 1 ; T[i] raz zliczony
K08:     Dla j = i+1,i+2,...,n-1 wykonuj K09 ; zliczanie rozpoczynamy od następnych elementów
K09:         Jeśli T[j] = W, to LL + 1  
K10:     Jeśli LmaxL, to idź do K13 ; zliczyliśmy więcej niż maxL?
K11:     maxLL ; jeśli tak, zapamiętujemy L w maxL
K12:     maxWW ; oraz W w maxW
K13:     ii + 1 ; przechodzimy do kolejnego elementu T[i]
K14: Pisz maxW,maxL ; wyprowadzamy wyniki
K15: Zakończ  

 

Rozwiązanie nr 3

Jeśli elementy zbioru tworzą spójny przedział wartości i przedział ten nie jest specjalnie duży, to do wyszukania wartości najczęstszej można zastosować następującą metodę.

 

Tworzymy tablicę L, której elementy będą pełniły rolę liczników wystąpień wartości elementów z tablicy T. Zakres indeksów w L możemy znaleźć wyszukując w tablicy T wartość minimalną i maksymalną (można też z góry przydzielić odpowiednią liczbę liczników, gdy znamy zakres wartości elementów w przeszukiwanej tablicy T). Zerujemy wszystkie liczniki w L i przeglądamy tablicę T zwiększając o 1 liczniki w L, które odpowiadają wartościom przeglądanych elementów. W efekcie po zakończeniu przeglądania tablicy T w L będziemy mieli informację o liczbie wystąpień każdej z wartości. Wyznaczamy w L element maksymalny. Wynikiem jest indeks, który określa wartość występującą najczęściej w T oraz zawartość elementu L o tym indeksie, która określa ile razy dana wartość wystąpiła w T.

 

Tak określony algorytm wyszukiwania najczęstszego elementu posiada liniową klasę złożoności obliczeniowej O(m + n), gdzie m jest liczbą wartości elementów przeszukiwanego zbioru, a n jest liczbą jego elementów.

 

Algorytm znajdowania najczęstszej wartości – wersja nr 3

Wejście
n      liczba elementów w tablicy T, n N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..
minZ  – minimalna wartość w T.
maxZ  – maksymalna wartość w T.
Wyjście:

Element występujący najczęściej w T oraz liczba jego wystąpień. Jeśli jest kilka elementów o takiej samej maksymalnej liczbie wystąpień, to algorytm w tej wersji zwraca najmniejszy z nich (jeśli pozostałe elementy są istotne, to można je odczytać z tablicy L porównując liczbę wystąpień z maksymalną).

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów T. i C
L  – tablica liczników wystąpień wartości elementów z T.
maxL  – tymczasowy element maksymalny w L
maxp  – pozycja tymczasowego elementu maksymalnego w L
Lista kroków:
K01: Utwórz L o rozmiarze maxZ - minZ + 1 ; przygotowujemy liczniki wartości
K02: Wyzeruj L ; liczniki ustawiamy na 0
K03: Dla i = 0,1,...,n-1 wykonuj K04 ; zliczamy wystąpienia wartości elementów
K04:      Zwiększ o 1 L[T[i] - minZ] ; w odpowiednich licznikach
K05: maxLL[0] ; szukamy max w L
K06: maxp ← 0  
K07: Dla i = 1,2,...,maxZ-minZ wykonuj K08...K10  
K08:     Jeśli L[i] ≤ maxL, to następny obieg pętli K07  
K09:     maxLL[i] ; zapamiętujemy wartość maksymalną
K10:     maxpi ; oraz jej pozycję
K11: Pisz maxp + minZ, maxL ; wyprowadzamy najczęstszy element oraz liczbę jego wystąpień
K12: Zakończ  

 

Wyszukiwanie lidera

W n-elementowym zbiorze T znaleźć element, którego wartość występuje więcej niż n/2 razy.

 

Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych wcześniej algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru T. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór T nie posiada lidera.

Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:

 

Jeśli zbiór T posiada lidera, to usunięcie z niego pary elementów różnych daje zbiór z tym samym liderem.
 

Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez nL liczbę elementów będących liderami. Zbiór T posiada n elementów, zatem liczba pozostałych elementów wynosi n - nL. Zachodzi nierówność:

 

nL > n - nL

 

Przypadek 1

Ze zbioru T usuwamy dwa elementy, które nie są liderami. W tym przypadku nL nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:

 

nL > (n - 2) - nL
nL > (n - nL) - 2

 

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż nL jest liczebnością liderów), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.

 

Przypadek 2

Ze zbioru T usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:

 

nL - 1 > (n - 2) - (nL - 1)
nL - 1 > n - 2 - nL + 1
nL - 1 > (n - nL) - 1

 

Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie ze zbioru jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.

 

Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.

 

Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:

 

Jeśli zbiór posiada lidera, to usunięcie z niego wszystkich par elementów różnych daje zbiór zawierający tylko elementy będące liderem.

Jeśli w wyniku takiej operacji otrzymujemy jednak zbiór pusty, to lidera w zbiorze wejściowym nie było.

 

Zamiast faktycznie wyrzucać ze zbioru elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:

 

Licznik elementów równych L ustawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L o 1. W przeciwnym razie licznik L zmniejszamy o 1 – odpowiada to wyrzuceniu ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.

Jeśli zbiór posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. Zatem licznik L powinien mieć zawartość większą od zera. Jeśli zawartość licznika L jest równa zero, to lidera w zbiorze nie ma. W przeciwnym razie zapamiętany element należy przeliczyć w zbiorze – jest to kandydat na lidera. Jeśli liczba jego wystąpień jest większa od liczby połowy elementów, to wytypowany element jest liderem. W przeciwnym razie zbiór T nie posiada lidera.

 

Algorytm posiada liniową klasę złożoności obliczeniowej O(n), jest zatem bardziej efektywny od opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości.

 

Algorytm wyszukiwania lidera w zbiorze

Wejście
n      liczba elementów w tablicy T, n N
T  – tablica do wyszukania najczęstszego elementu Elementy są liczbami całkowitymi. Indeksy od 0 do n - 1..
Wyjście:

Element będący liderem, liczba jego wystąpień w T lub informacja o braku lidera.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów T. i C
L  – licznik wystąpień wartości równych, L C
W  – wartość lidera
Lista kroków:
K01: L ← 0 ; licznik wartości równych
K02: Dla i = 0,1,...,n-1 wykonuj K03...K07 ; przeglądamy kolejne elementy
K03:     Jeśli L > 0, to idź do K07 ; sprawdzamy, czy licznik równy 0
K04:     WT[i] ; jeśli tak, zapamiętujemy bieżący element
K05:     L ← 1 ; zaliczamy ten element
K06:     Następny obieg pętli K02  
K07:     Jeśli W = T[i], to LL + 1
    inaczej LL - 1
; elementy równe zliczamy
; elementy różne wyrzucamy
K08: Jeśli L = 0, to idź do K15 ; sprawdzamy, czy jest kandydat na lidera
K09: L ← 0 ; jeśli tak, to sprawdzamy, czy jest liderem
K10: Dla i = 0,1,...,n-1 wykonuj K11 ; zliczamy jego wystąpienia w zbiorze
K11:     Jeśli T[i] = W, to LL + 1  
K12: Jeśli L ≤ [n:2], to idź do K15 ; lider?
K13 Pisz W,L ; wyprowadzamy lidera oraz liczbę jego wystąpień
K14: Zakończ  
K15: Pisz "BRAK LIDERA"  
K16: Zakończ  

Dane do ćwiczeń

800
0 1 2 3 2 2 3 3 3 3 2 0 0 3 1 3 1 3 1 0
1 3 1 0 3 3 0 3 2 2 3 3 3 2 0 3 3 3 3 2
2 3 3 1 0 1 3 1 3 2 3 3 0 3 2 3 3 0 0 3
1 0 0 3 3 3 3 3 0 3 2 3 0 2 1 1 3 0 3 3
3 2 1 3 3 2 1 0 3 3 1 3 0 2 3 1 3 1 1 3
3 3 1 3 1 2 0 0 2 3 0 2 1 2 3 3 0 1 3 3
1 2 0 1 3 2 1 3 3 3 3 1 3 1 1 2 0 2 1 1
3 3 3 3 0 2 3 3 3 1 3 3 2 2 3 0 3 3 0 2
3 1 3 3 3 3 3 1 3 3 0 0 2 0 2 3 2 1 3 3
0 3 3 3 0 3 3 3 0 3 1 0 2 3 3 1 3 3 3 0
3 0 3 2 3 2 0 0 3 2 0 2 0 3 2 3 3 0 3 1
3 2 3 3 3 3 0 3 0 3 0 2 3 3 0 1 3 3 1 0
3 3 0 0 0 3 3 2 3 3 3 1 0 3 2 3 3 3 3 0
3 3 3 1 2 3 3 1 3 3 3 3 3 2 3 3 3 2 3 1
3 3 1 3 3 0 3 1 3 3 1 0 2 3 3 3 2 3 1 3
2 3 2 1 3 2 3 0 3 3 3 0 3 0 2 3 0 1 2 3
2 3 2 1 3 3 3 1 0 3 0 0 1 1 1 2 0 3 1 2
3 3 2 3 0 1 3 3 3 3 0 1 0 1 3 0 2 2 3 2
3 2 3 0 1 3 3 3 2 2 3 0 0 1 3 0 3 3 1 3
0 3 0 0 3 3 3 2 1 3 0 2 1 3 1 3 2 3 0 3
0 2 1 0 3 1 2 2 3 3 3 3 0 3 3 0 3 3 1 1
3 3 3 2 0 3 1 2 0 0 3 3 3 2 3 3 2 3 2 3
3 1 3 2 0 3 3 3 1 3 0 3 0 3 1 1 3 3 3 1
1 1 1 1 2 3 3 2 3 0 3 3 0 3 3 1 3 2 3 3
2 1 3 0 0 3 0 3 3 0 0 3 2 0 1 3 3 3 2 1
0 3 3 3 3 1 3 3 3 2 3 1 2 3 2 3 3 3 3 2
3 2 2 1 0 3 3 3 3 3 3 2 1 2 1 3 3 3 3 3
3 3 2 3 3 1 3 1 3 3 3 3 2 0 2 3 3 3 2 3
3 3 3 1 3 2 1 2 3 3 2 3 3 3 1 1 3 3 0 3
0 3 2 3 3 2 3 2 1 3 3 0 1 1 3 3 1 3 3 3
2 1 3 3 3 0 3 3 3 0 3 2 1 3 3 3 2 3 3 1
3 3 3 0 2 0 2 1 1 2 0 3 0 2 3 0 0 3 0 3
1 3 3 1 3 3 2 3 0 3 0 0 0 2 2 1 3 2 1 3
3 1 2 3 0 2 3 0 3 3 3 0 2 2 3 2 3 3 3 3
3 1 3 3 3 3 3 1 0 1 1 1 1 0 0 3 1 3 1 3
3 2 3 2 3 3 2 3 3 3 2 0 3 0 1 0 1 3 0 0
3 2 3 0 3 1 3 3 3 1 3 3 0 0 2 3 3 0 3 3
0 3 3 0 1 0 1 0 2 3 0 3 2 0 1 3 0 2 1 3
2 3 0 0 2 3 1 1 3 1 1 0 3 3 3 3 0 2 3 0
3 3 2 3 3 3 0 3 3 3 0 3 2 3 3 1 3 0 1 1

 

 


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.