Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0
©2008 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek
|
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.
| n | - | liczba elementów |
| T[ ] | - | tablica n elementowa zawierająca przeszukiwane elementy zbioru |
| v | - | poszukiwana wartość elementów |
Lv - liczba wystąpień elementu o wartości v w T[ ].
| 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
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++.
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++.
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++.
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:
 | I Liceum Ogólnokształcące |
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