Wpisany przez Michał Witaszek,
19 lipca 2011 12:02
Dominantą nazywamy najczęściej występującą wartość w zbiorze. Aby ją odnaleźć, sporządzimy listę liczb występujących w tablicy. Niech T[] będzie tablicą, w której szukamy dominantę, L[] będzie tablicą, w której będziemy przechowywać wartości znalezione w tablicy T[], a W[] tablicą, w której będziemy przechowywać ilość wystąpień danej liczby.
Na początku tablice L[] oraz W[], są puste. By znaleźć dominantę będziemy przeszukiwać zadaną tablicę T[]. Każdą nową wartość dopiszemy do listy L[] (listę liczb potraktujemy jak stos), oraz ustawimy ilość wystąpień liczby W[] na 1. Jeśli kolejna liczba z tablicy T[], będzie już znajdowała się na liście L[], wówczas tylko zwiększymy ilość jej wystąpień w tablicy W[] o 1.
Dany jest zbiór liczb: T = {1, 4, 6, 5, 4, 1, 5, 4}.
Na początku tablica L oraz W są puste.
Bierzemy pierwszy element z tablicy T jest to 1, nie ma jej w tablicy L, a więc dodajemy ją tam i jednocześnie do tablicy W wstawiamy 1 (póki co jedynka występowała tylko raz)
L = {1} oraz W = {1}
Bierzemy kolejny element, tym razem jest to 4, nie mam jej w tablicy L, a więc postępujemy analogicznie jak poprzednio:
L = {1, 4} oraz W = {1, 1}
Bierzemy następny element, jest to 6, nie mam jej w tablicy L, a więc postępujemy tak samo jak poprzednio:
L = {1, 4, 6} oraz W = {1, 1, 1}
Bierzemy kolejny element, jest to 5, nie mam jej w tablicy L, a więc postępujemy znów tak samo:
L = {1, 4, 6, 5} oraz W = {1, 1, 1, 1}
Bierzemy kolejny element, jest to 4, znajduje się ona w tablicy L pod drugim indeksem, a więc teraz nie modyfikujemy tablicy L, lecz zwiększamy o jeden wartość pod indeksem drugim w tablicy W:
L = {1, 4, 6, 5} oraz W = {1, 2, 1, 1}
Bierzemy kolejny element, jest to 1, znajduje się ona w tablicy L pod pierwszym indeksem, a więc zwiększamy o jeden wartość pod pierwszym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 2, 1, 1}
Bierzemy kolejny element, jest to 5, znajduje się ona w tablicy L pod indeksem czwartym, a więc zwiększamy o jeden wartość pod tym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 2, 1, 2}
Bierzemy kolejny element, jest to 4, znajduje się ona w tablicy L pod indeksem drugim, a więc zwiększamy o jeden wartość pod tym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 3, 1, 2}
Był to ostatni element z tablicy T. Wynik należy odczytać następująco:
Liczba 1 w zbiorze pojawia się 2 razy,
Liczba 4 - 3 razy,
Liczba 6 - 1 raz,
Liczba 5 - 2 razy.
By określić która liczba najczęściej pojawia się w tablicy, musimy odnaleźć największą wartość w tablicy W[]. W tym przypadku, z pośród liczb {2, 3, 1, 2} największą jest 3. Liczba znajduje w tablicy W[] pod indeksem drugim. Sprawdzamy wartość pod indeksem 2 na liście L[], jest to 4. Szukaną dominantą jest liczba 4, która w zbiorze pojawia się 3 razy.
Inny przykład:
Dany jest zbiór liczb: {1, 6, 7, 2, 1, 7, 4, 7, 3},
Lista liczb występujących w zbiorze: {1, 6, 7, 2, 4, 3}
Występowanie liczb w zbiorze: {2, 1, 3, 1, 1, 1}
Dominantą jest liczba 7, pojawia się 3 razy.
Na początku tablice L[] oraz W[], są puste. By znaleźć dominantę będziemy przeszukiwać zadaną tablicę T[]. Każdą nową wartość dopiszemy do listy L[] (listę liczb potraktujemy jak stos), oraz ustawimy ilość wystąpień liczby W[] na 1. Jeśli kolejna liczba z tablicy T[], będzie już znajdowała się na liście L[], wówczas tylko zwiększymy ilość jej wystąpień w tablicy W[] o 1.
Przykład:
Dany jest zbiór liczb: T = {1, 4, 6, 5, 4, 1, 5, 4}.
Na początku tablica L oraz W są puste.
Bierzemy pierwszy element z tablicy T jest to 1, nie ma jej w tablicy L, a więc dodajemy ją tam i jednocześnie do tablicy W wstawiamy 1 (póki co jedynka występowała tylko raz)
L = {1} oraz W = {1}
Bierzemy kolejny element, tym razem jest to 4, nie mam jej w tablicy L, a więc postępujemy analogicznie jak poprzednio:
L = {1, 4} oraz W = {1, 1}
Bierzemy następny element, jest to 6, nie mam jej w tablicy L, a więc postępujemy tak samo jak poprzednio:
L = {1, 4, 6} oraz W = {1, 1, 1}
Bierzemy kolejny element, jest to 5, nie mam jej w tablicy L, a więc postępujemy znów tak samo:
L = {1, 4, 6, 5} oraz W = {1, 1, 1, 1}
Bierzemy kolejny element, jest to 4, znajduje się ona w tablicy L pod drugim indeksem, a więc teraz nie modyfikujemy tablicy L, lecz zwiększamy o jeden wartość pod indeksem drugim w tablicy W:
L = {1, 4, 6, 5} oraz W = {1, 2, 1, 1}
Bierzemy kolejny element, jest to 1, znajduje się ona w tablicy L pod pierwszym indeksem, a więc zwiększamy o jeden wartość pod pierwszym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 2, 1, 1}
Bierzemy kolejny element, jest to 5, znajduje się ona w tablicy L pod indeksem czwartym, a więc zwiększamy o jeden wartość pod tym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 2, 1, 2}
Bierzemy kolejny element, jest to 4, znajduje się ona w tablicy L pod indeksem drugim, a więc zwiększamy o jeden wartość pod tym indeksem w tablicy W:
L = {1, 4, 6, 5} oraz W = {2, 3, 1, 2}
Był to ostatni element z tablicy T. Wynik należy odczytać następująco:
Liczba 1 w zbiorze pojawia się 2 razy,
Liczba 4 - 3 razy,
Liczba 6 - 1 raz,
Liczba 5 - 2 razy.
By określić która liczba najczęściej pojawia się w tablicy, musimy odnaleźć największą wartość w tablicy W[]. W tym przypadku, z pośród liczb {2, 3, 1, 2} największą jest 3. Liczba znajduje w tablicy W[] pod indeksem drugim. Sprawdzamy wartość pod indeksem 2 na liście L[], jest to 4. Szukaną dominantą jest liczba 4, która w zbiorze pojawia się 3 razy.
Inny przykład:
Dany jest zbiór liczb: {1, 6, 7, 2, 1, 7, 4, 7, 3},
Lista liczb występujących w zbiorze: {1, 6, 7, 2, 4, 3}
Występowanie liczb w zbiorze: {2, 1, 3, 1, 1, 1}
Dominantą jest liczba 7, pojawia się 3 razy.
Przykład w JavaScript:
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Kasia Pastwa | C# | Visual Studio 2012 wraz z dostępnymi funkcjami | .cs | .cs | ***** / 5 |
Michał Witaszek | C/C++ | .cpp | .cpp | ***** / 11 | |
Michał Witaszek | Delphi/Pascal | .pas | .pas | ***** / 5 | |
Dominik Goździuk | Java | .java | .java | ***** / 6 | |
Yupk | JavaScript | .js | .js | ***** / 1 | |
Dominik Goździuk | Perl | .pl | .pl | ***** / 2 | |
Dominik Goździuk | Php | .php | .php | ***** / 1 | |
Dariusz Rorat | Python | .py | .py | ***** / 0 |
Poprawiony: 20 października 2015 10:06