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(n²). 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 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ć.

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:

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:

Wyszukiwanie lidera

W n-elementowym zbiorze T  znaleźć element, którego wartość występuje więcej niż ⁿ/₂ 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:

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

n_L  > n  - n_L

Przypadek 1

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

Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż n_L  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:

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:

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:	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

 

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