Zliczanie

Zliczanie (ang. counting) jest równoważne wyszukiwaniu. Tworzymy licznik elementów, który wstępnie zostaje wyzerowany. Następnie przeglądamy kolejne elementy zbioru w poszukiwaniu tych, które spełniają zadane kryterium. Gdy znajdziemy odpowiedni element, zwiększamy stan licznika i wyszukiwanie kontynuujemy od następnego elementu. Wynikiem jest zawartość licznika, czyli liczba elementów w zbiorze spełniających podane kryterium.

W naszym algorytmie kryterium zliczania jest to, iż element zbioru jest równy kluczowi k. W rzeczywistości kryteria mogą być zupełnie inne, np. zliczamy wszystkie elementy zbioru o wartości większej od średniej arytmetycznej wszystkich elementów, zliczamy elementy podzielne przez k, itp.

 

Algorytm zliczania liniowego

Wejście
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.
p  – indeks pierwszego elementu Z[ ], od którego rozpoczniemy poszukiwania. p C
k  – poszukiwana wartość, czyli tzw. klucz, wg którego zliczamy elementy w Z[ ]
Wyjście:

Liczba elementów zbioru równych k.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. i   C
L  – licznik znalezionych elementów, L   C
Lista kroków:
K01: L ← 0 ; zerujemy licznik
K02: Dla i = p,p+1,...,n-1: wykonuj K03 ; przeglądamy kolejne elementy w zbiorze
K03:     Jeśli Z[i] = k, to LL + 1 ; zliczamy elementy spełniające kryterium
K04: Zakończ z wynikiem L  

 

Najczęstsza wartość w zbiorze

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 Z, 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 Z[ ], n N
Z[ ]  – 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 Z[ ] 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 Z[ ]. i,j C
L  – licznik wystąpień wartości elementu, L C
W  – wartość elementu, której liczbę wystąpień w Z[ ] zliczamy.
maxW  – najczęstsza wartość elementów tablicy Z[ ]
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 Z[ ]
K03:     WZ[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 Z[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  

 

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

 

  1. Ze zbioru bierzemy KAŻDY element Z[i] i zliczamy wystąpienia jego wartości W w CAŁYM zbiorze Z[ ]. 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 Z[0] (dlaczego?).
  2. Każdy element Z[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 Z[ ], 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 Z[ ], n N
Z[ ]  – 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 Z[ ] 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 Z[ ]. i,j C
L  – licznik wystąpień wartości elementu, L C
W  – wartość elementu, której liczbę wystąpień w Z[ ] zliczamy.
maxW  – najczęstsza wartość elementów tablicy Z[ ]
maxL  – liczba wystąpień wartości najczęstszej. maxL C
Lista kroków:
K01: maxL ← 0 ; licznik wystąpień najczęstszej wartości
K02: maxWZ[0] - 1 ; najczęstsza wartość - musi być różna od Z[0]!
K03: i ← 0 ; rozpoczynamy zliczanie wartości elementów
K04: Dopóki i < n - maxL, wykonuj K05...K13 ; zliczamy do n-maxL
K05:     WZ[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 Z[i]
K07:     L ← 1 ; Z[i] raz zliczony
K08:     Dla j = i+1,i+2,...,n-1 wykonuj K09 ; zliczanie rozpoczynamy od następnych elementów
K09:         Jeśli Z[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 Z[i]
K14: Pisz maxW,maxL ; wyprowadzamy wyniki
K15: Zakończ  

 

Wyszukiwanie lidera

W n-elementowym zbiorze Z 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 w poprzednim rozdziale 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 Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.

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

 

Jeśli zbiór Z 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 Z posiada n elementów, zatem liczba pozostałych elementów wynosi n - nL. Zachodzi nierówność:

nL > n - nL

 

Przypadek 1

Ze zbioru Z 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 Z 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 Z 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 Z[ ], n N
Z[ ]  – 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 Z[ ] lub informacja o braku lidera.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z[ ]. 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:     WZ[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 = Z[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 Z[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  

 



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.