Wyszukiwanie dominanty zbioru

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 jego 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.

 

Algorytm znajdowania najczęstszej wartości - wersja 1

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

maxW - wartość najczęściej powtarzającego się elementu.
maxC - liczba powtórzeń wartości maxW w tablicy T[ ].

Zmienne pomocnicze
i, j  -  przebiega przez kolejne indeksy elementów T[ ]. i,jC
c  - licznik wystąpień wartości elementu, cC
w  - wartość elementu, której liczbę wystąpień w T[ ] zliczamy.
Lista kroków:
Krok 1: maxC ← 0 ; zerujemy maksymalną liczbę wystąpień
Krok 2: i ← 0 ; przeglądanie rozpoczynamy od pierwszego elementu tablicy
Krok 3: Jeśli in, to zakończ  
Krok 4: wT[i] ; zapamiętujemy poszukiwaną wartość elementu
Krok 5: c ← 0 ; zerujemy jej licznik wystąpień
Krok 6: j ← 0  
Krok 7: Jeśli jn, to idź do kroku 11  
Krok 8: Jeśli T[j] = w, to cc + 1 ; zliczamy wystąpienia w
Krok 9: jj + 1  
Krok 10: Idź do kroku 7  
Krok 11: Jeśli cmaxC, to idź do kroku 14 ; sprawdzamy, czy w jest tymczasowo najczęstsze
Krok 12: maxCc ; jeśli tak, zapamiętujemy liczbę wystąpień
Krok 13: maxWw ; oraz wartość w
Krok 14: ii + 1  
Krok 15: Idź do kroku 3  

 

Przykładowe dane dla programu

Pierwsza liczba określa liczbę n elementów w zbiorze. Następne n liczb to elementy zbioru, które są liczbami całkowitymi z zakresu od 0 do 999.

510
463 926 603 901 826 879 376 264 189 10 582 447 664 547 702
453 401 398 10 907 177 256 105 429 63 995 437 638 10 16
16 320 40 141 523 284 138 405 17 318 257 543 651 378 278
9 27 805 962 10 390 387 382 210 32 64 128 10 150 200
4 12 32 530 35 125 450 41 316 301 15 246 849 844 165
27 959 14 21 8 876 539 948 662 5 13 32 254 577 888
452 715 10 81 725 359 361 381 263 793 144 412 137 119 476
496 189 467 149 377 714 273 443 490 81 976 255 180 71 703
620 161 978 849 678 964 935 188 602 63 659 111 182 245 712
31 9 8 603 178 832 743 916 341 87 65 646 707 830 612
63 877 495 149 290 2 698 166 227 400 476 941 786 129 71
919 820 502 828 481 943 815 70 415 413 484 1 329 250 78
915 466 401 641 802 543 10 766 934 487 786 868 951 768 886
231 762 74 269 508 10 134 328 371 937 531 756 470 464 488
926 25 502 261 339 115 67 962 399 68 882 863 996 791 924
742 13 370 448 183 531 147 41 546 768 318 120 522 466 628
756 968 58 358 592 421 638 978 980 988 444 85 118 831 48
858 754 281 344 210 703 84 885 844 685 148 389 927 84 956
103 310 782 175 614 523 496 897 10 399 924 896 539 328 995
685 336 548 961 15 175 982 120 300 100 583 228 588 672 950
68 232 659 587 909 967 218 608 838 779 343 873 980 478 572
950 944 395 754 598 994 26 689 399 342 3 4 5 982 730
985 780 160 816 933 628 433 414 845 646 322 450 716 849 619
669 855 278 173 687 471 304 460 377 424 10 7 20 130 721
883 654 47 145 224 771 927 10 579 38 361 773 661 662 155
335 9 159 283 49 971 963 318 913 431 811 266 374 861 284
232 672 564 888 932 484 973 226 143 344 962 110 444 532 646
16 3 29 14 83 874 871 401 381 473 538 908 58 760 20
969 120 160 40 584 176 598 110 358 443 822 403 10 46 199
643 614 574 5 8 13 4 8 3 143 703 7 242 50 61
34 487 526 290 818 219 968 710 894 510 180 447 708 226 296
782 314 932 211 169 67 824 10 90 508 138 350 824 799 882
713 212 335 223 990 735 502 743 363 434 484 10 782 166 512
565 654 934 364 397 168 4 5 6 603 524 183 303 10 399

 

Program wyszukiwania dominanty - wersja 1

 

// Wyszukiwanie dominanty
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int * T,n,i,j,c,w,maxc,maxw;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy najczęstszego elementu

    maxc = 0;

    for(i = 0; i < n; i++)
    {
        w = T[i];
        c = 0;

        for(j = 0; j < n; j++) if(w == T[j]) c++;

        if(c > maxc)
        {
            maxc = c;
            maxw = w;
        }
    }

    // wyświetlamy wyniki

    cout << "\nElement " << maxw << " wystepuje " << maxc << " razy.\n\n";

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

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 dla CAŁEGO zbioru T[ ]. W ten sposób najczęstsza wartość maxW zostanie zliczona maxC2 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 maxC mamy chwilową maksymalną liczbę wystąpień pewnej wartości maxW, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n - maxC. 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 maxC, gdyż braknie elementów.

Oczywiście, powyższe ulepszenia nie zmienią klasy złożoności obliczeniowej - otrzymamy jedynie nieco szybszy algorytm, który bardziej efektywnie rozwiązuje nasz problem.

 

Algorytm znajdowania najczęstszej wartości - wersja 2

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

maxW - wartość najczęściej powtarzającego się elementu.
maxC - liczba powtórzeń wartości maxW w tablicy T[ ].

Zmienne pomocnicze
i, j  -  przebiega przez kolejne indeksy elementów T[ ]. i,jC
c  - licznik wystąpień wartości elementu, cC
w  - wartość elementu, której liczbę wystąpień w T[ ] zliczamy.
Lista kroków:
Krok 1: maxC ← 0 ; zerujemy maksymalną liczbę wystąpień
Krok 2: maxW ← T[0] - 1 ; zapewniamy, iż maxw zawiera wartość różną od T[0]
Krok 3: i ← 0 ; przeglądanie rozpoczynamy od pierwszego elementu tablicy
Krok 4: Jeśli in - maxC, to zakończ  
Krok 5: wT[i] ; zapamiętujemy poszukiwaną wartość elementu
Krok 6: c ← 1 ; zerujemy jej licznik wystąpień
Krok 7: j ← i + 1 ; zliczanie rozpoczynamy od pozycji następnej
Krok 8: Jeśli jn, to idź do kroku 12  
Krok 9: Jeśli T[j] = w, to cc + 1 ; zliczamy wystąpienia w
Krok 10: jj + 1  
Krok 11: Idź do kroku 8  
Krok 12: Jeśli cmaxC, to idź do kroku 15 ; sprawdzamy, czy w jest tymczasowo najczęstsze
Krok 13: maxCc ; jeśli tak, zapamiętujemy liczbę wystąpień
Krok 14: maxWw ; oraz wartość w
Krok 15: ii + 1  
Krok 16: Idź do kroku 4  

 

Program wyszukiwania dominanty - wersja 2

 

// Wyszukiwanie dominanty
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int * T,n,i,j,c,w,maxc,maxw;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy najczęstszego elementu

    maxc = 0;
    maxw = T[0] - 1;

    for(i = 0; i < n - maxc; i++)
    {
        w = T[i];
        if(w != maxw)
        {
            c = 1;

            for(j = i + 1; j < n; j++) if(w == T[j]) c++;

            if(c > maxc)
            {
                maxc = c;
                maxw = w;
            }
        }
    }

    // wyświetlamy wyniki

    cout << "\nElement " << maxw << " wystepuje " << maxc << " razy.\n\n";

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 



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.