Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

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

Algorytm znajdowania najczęstszej wartości - wersja 1

Wejście

Wyjście:

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

Zmienne pomocnicze

Lista kroków:

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ść max_W  zostanie zliczona max_C² razy. Zatem pierwsze ulepszenie będzie polegało na tym, iż pobrany element w  zbioru zliczamy tylko wtedy, gdy jest on różny od max_W. Wynika z tego, iż na początku pracy algorytmu do max_W  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 max_C  mamy chwilową maksymalną liczbę wystąpień pewnej wartości max_W, to zliczanie nowych elementów możemy przerwać po osiągnięciu pozycji n  - max_C. 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 max_C, 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

Wyjście:

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

Zmienne pomocnicze

Lista kroków:

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;
}

---

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