Informatyka dla klas II

Wyszukiwanie najczęstszego elementu w zbiorze

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 obrazek 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 obrazek C
L  – licznik wystąpień wartości elementu, L obrazek 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 obrazek 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 L  ← L  + 1  
K07:     Jeśli L  ≤ maxL, to następny obieg pętli K2 ; sprawdzamy, czy W jest tymczasowo najczęstsze
K08:     maxL  ← L ; jeśli tak, zapamiętujemy liczbę wystąpień
K09:     maxW  ← W ; 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 obrazek 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 obrazek C
L  – licznik wystąpień wartości elementu, L obrazek 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 obrazek 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 L  ← L  + 1  
K10:     Jeśli L  ≤ maxL, to idź do K13 ; zliczyliśmy więcej niż maxL?
K11:     maxL  ← L ; jeśli tak, zapamiętujemy L w maxL
K12:     maxW  ← W ; oraz W w maxW
K13:     i  ← i  + 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 obrazek 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 obrazek 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: maxL  ← L[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:     maxL  ← L[i] ; zapamiętujemy wartość maksymalną
K10:     maxp  ← i ; 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 obrazek 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 obrazek C
L  – licznik wystąpień wartości równych, L obrazek 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:     W  ← T[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 L  ← L  + 1
    inaczej L  ← L  - 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 L  ← L  + 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

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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