Wyszukiwanie lidera

Zliczanie wystąpień elementu

Zadanie jest następujące:

W zbiorze T zliczyć wszystkie wystąpienia elementu o wartości v.

Problem ten możemy prosto rozwiązać modyfikując nieznacznie poznane algorytmy wyszukiwania. Postępujemy następująco:

Tworzymy licznik i inicjujemy go na zero. Przeglądamy kolejne elementy zbioru. Przeglądany element porównujemy z wartością v. Jeśli występuje zgodność, to zwiększamy licznik o jeden. Po przeglądnięciu wszystkich elementów w zbiorze licznik będzie zawierał liczbę wystąpień elementów o wartości v.

 

Algorytm zliczania wystąpień elementu o zadanej wartości

Wejście:
n  -  liczba elementów
T[ ]  - tablica n elementowa zawierająca przeszukiwane elementy zbioru
v  - poszukiwana wartość elementów
Wyjście:

Lv - liczba wystąpień elementu o wartości v w T[ ].

Lista kroków:
K01: Lv ← 0 ; inicjujemy licznik wystąpień v
K02: Dla i = 0,1,...,n-1: wykonuj
    Jeśli T[i] = v, to Lv ← Lv + 1
; dla każdego znalezionego elementu o wartości v
; zwiększamy o 1 licznik wystąpień Lv
K03: Pisz Lv  
K04: Zakończ  

Program:

Ćwiczenie na lekcji

 

Ćwiczenia

  1. Wykorzystując podany algorytm zliczania wystąpień elementu zaprojektuj algorytm, który wyznaczy liczbę wystąpień wszystkich wartości w zbiorze T. Dana wartość powinna być zliczana tylko jeden raz. Określ klasę złożoności obliczeniowej swojego rozwiązania. Na podstawie tego algorytmu napisz odpowiedni program w języku C++.

  2. Wykorzystując algorytm z zadania 1 zaprojektuj nowy algorytm, który wyznaczy najczęstszą wartość w zbiorze. Określ klasę jego złożoności obliczeniowej. Na podstawie algorytmu napisz odpowiedni program w języku C++.

  3. Wykorzystując algorytm z zadania 2 zaprojektuj nowy algorytm, który sprawdzi, czy w zbiorze występuje wartość v, której liczba wystąpień przekracza n/2, gdzie n jest liczbą elementów zbioru. Jeśli tak, to algorytm powinien wyszukać tę wartość, w przeciwnym razie powinien być tworzony odpowiedni komunikat. Na podstawie algorytmu napisz odpowiedni program w języku C++.

 

Wyszukiwanie lidera

W ćwiczeniu nr 3 stworzyliśmy algorytm, który w zbiorze T wyszukiwał element v o liczbie wystąpień większej niż połowa elementów tego zbioru. Element o takiej własności nazywamy liderem (ang. leader - przywódca). Nasz algorytm nie jest specjalnie efektywny. Istnieje inny algorytm wyszukiwania lidera, który posiada liniową złożoność obliczeniową. Opiera się on na następującym twierdzeniu:

 

 

 

 

 

 

 

 

 



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.