Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemW n-elementowym zbiorze Z należy wyszukać element, którego wartość występuje więcej niż n/2 razy. |
Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.
Istnieje jednakże prostszy i szybszy algorytm, który korzysta z następującego twierdzenia:
Jeśli zbiór Z posiada lidera, to usunięcie z niego pary elementów różnych daje zbiór z tym samym liderem. |
Dowód tego twierdzenia jest bardzo prosty. Oznaczmy przez nL liczbę elementów będących liderami. Zbiór Z posiada n elementów, zatem liczba pozostałych elementów wynosi n - nL. Zachodzi nierówność:
nL> n - nL
Przypadek 1
Ze zbioru Z usuwamy dwa elementy, które nie są liderami. W tym przypadku nL nie zmniejsza się, lecz zmniejsza się o 2 liczba elementów n. Otrzymamy zatem:
nL > (n - 2) - nL nL > (n - nL) - 2
Jeśli pierwsza nierówność była prawdziwa (a była z założenia, iż nL jest liczebnością liderów), to tym bardziej będzie prawdziwa druga nierówność. Wynika z tego, iż usunięcie dwóch elementów nie będących liderami nie wpływa na występowanie lidera.
Przypadek 2
Ze zbioru Z usuwamy jeden element lidera oraz jeden element nie będący liderem. Zmniejszeniu o 1 ulega zatem liczba liderów, a liczba elementów maleje o 2. Otrzymujemy:
nL - 1 > (n - 2) - (nL - 1) nL - 1 > n - 2 - nL + 1 nL - 1 > (n - nL) - 1
Otrzymaliśmy nierówność wyjściową, w której od obu stron odjęto tę samą liczbę -1. Zatem nierówność jest wciąż prawdziwa, z czego wynika, iż usunięcie ze zbioru jednego lidera i jeden element nie będący liderem nie wpływa na występowanie lidera.
Innych przypadków nie ma, zatem dowiedliśmy prawdziwości twierdzenia.
Z powyższego twierdzenia bezpośrednio wynikają dwie dalsze własności:
Jeśli zbiór posiada lidera, to usunięcie z niego wszystkich par elementów różnych daje zbiór
zawierający tylko elementy będące liderem. Jeśli w wyniku takiej operacji otrzymujemy jednak zbiór pusty, to lidera w zbiorze wejściowym nie było. |
Zamiast faktycznie wyrzucać ze zbioru elementy różne – co jest dosyć trudne, możemy wykonać operację odwrotną. Będziemy zliczali elementy o równych wartościach – wystarczy wtedy zapamiętać wartość elementu oraz ilość jej wystąpień. Algorytm pracuje w sposób następujący:
Licznik elementów równych L ustawiamy na zero. Rozpoczynamy przeglądanie elementów zbioru od pierwszego do ostatniego. Jeśli licznik elementów równych L jest równy 0, to kolejny element zbioru zapamiętujemy, zwiększamy licznik L o 1 i wykonujemy kolejny obieg pętli dla następnego elementu. Jeśli licznik L nie jest równy zero, to sprawdzamy, czy bieżący element jest równy zapamiętanemu. Jeśli tak, to mamy dwa elementy równe – zwiększamy licznik L o 1. W przeciwnym razie licznik L zmniejszamy o 1 – odpowiada to wyrzuceniu ze zbioru dwóch elementów różnych. W obu przypadkach wykonujemy kolejny obieg pętli.
Jeśli zbiór Z posiadał lidera, to liczba elementów równych jest większa od liczby elementów różnych. W takim przypadku zapamiętana wartość jest liderem. Aby to potwierdzić, zliczamy liczbę wystąpień tej wartości w zbiorze Z. Jeśli jest ona większa od liczby połowy elementów, to mamy lidera. W przeciwnym razie zbiór Z nie posiada lidera.
Algorytm posiada liniową klasę złożoności obliczeniowej O(n), jest zatem bardziej efektywny od opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości.
K01: L ← 0 ; licznik wartości równych K02: Dla i = 0, 1, …, n-1: ; przeglądamy kolejne elementy wykonuj kroki K03…K07 K03: Jeśli L > 0, ; sprawdzamy, czy licznik równy 0 to idź do kroku K07 K04: W ← Z[i] ; jeśli tak, zapamiętujemy ; bieżący element K05: L ← 1 ; zaliczamy ten element K06: Następny obieg pętli K02 K07: Jeśli W = Z[i], ; elementy równe zliczamy to L ← L + 1 inaczej L ← L - 1 ; elementy różne wyrzucamy K08: Jeśli L = 0, ; sprawdzamy, czy jest to idź do kroku K15 ; kandydat na lidera K09: L ← 0 ; jeśli tak, to sprawdzamy, ; czy jest liderem K10: Dla i = 0, 1, …, n-1: ; zliczamy jego wystąpienia wykonuj krok K11 ; w zbiorze K11: Jeśli Z[i] = W, to L ← L + 1 K12: Jeśli L ≤ [n:2], ; lider? to idź do kroku K15 K13: Pisz W, L ; wyprowadzamy lidera oraz ; liczbę jego wystąpień K14: Zakończ K15: Pisz "BRAK LIDERA" K16: Zakończ
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program umieszcza w tablicy Z 80 liczb pseudolosowych z zakresu od 0 do 99 w taki sposób, aby mógł się pojawić w niej lider. Następnie program wyszukuje lidera podanym powyżej algorytmem, wyświetla zawartość tablicy z zaznaczonym liderem i wypisuje jego wartość oraz liczbę wystąpień. Jeśli pomimo wszystko zdarzy się, iż w tablicy Z nie będzie lidera, program wypisze tekst BRAK LIDERA. |
Pascal// Wyszukiwanie lidera // Data: 4.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- program prg; const N = 80; var Z : array [0..N-1] of integer; i, L, W : integer; t : boolean; begin randomize; // Wypełniamy tablicę W := random(100); for i := 0 to N - 1 do if random(2) = 1 then Z[i] := random(100) else Z[i] := W; // Wyszukujemy lidera L := 0; for i := 0 to N - 1 do if L = 0 then begin W := Z[i]; L := 1; end else if W = Z[i] then inc(L) else dec(L); // Sprawdzamy, czy mamy lidera if L = 0 then t := false else begin L := 0; for i := 0 to N-1 do if W = Z[i] then inc(L); t := L > N div 2; end; // Wyświetlamy tablicę for i := 0 to N - 1 do if t and (Z[i] = W) then write (' >', Z[i]:2) else write (Z[i]:4); // Wyświetlamy wyniki writeln; if t then writeln(W, ' : ', L) else writeln('BRAK LIDERA'); writeln end. |
// Wyszukiwanie lidera // Data: 4.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> #include <cstdlib> #include <ctime> using namespace std; const int N = 80; int main() { int Z[N], i, L, W; bool t; srand(time(NULL)); // Wypełniamy tablicę W = rand() % 100; for(i = 0; i < N; i++) if(rand() % 2) Z[i] = rand() % 100; else Z[i] = W; // Wyszukujemy lidera L = 0; for(i = 0; i < N; i++) if(!L) { W = Z[i]; L = 1; } else if(W == Z[i]) L++; else L--; // Sprawdzamy, czy mamy lidera if(!L) t = false; else { L = 0; for(i = 0; i < N; i++) if(W == Z[i]) L++; t = L > N/2; } // Wyświetlamy tablicę for(i = 0; i < N; i++) if(t && (Z[i] == W)) cout << " >" << setw(2) << Z[i]; else cout << setw(4) << Z[i]; // Wyświetlamy wyniki cout << endl; if(t) cout << W << " : " << L << endl; else cout << "BRAK LIDERA\n"; cout << endl; return 0; } |
Basic' Wyszukiwanie lidera ' Data: 4.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Const N = 80 Dim As Integer Z(N-1), i, L, W, t Randomize ' Wypełniamy tablicę W = Cint(Rnd * 99) For i = 0 To N-1 If Rnd > 0.5 Then Z(i) = Cint(Rnd * 99) Else Z(i) = W End If Next ' Wyszukujemy lidera L = 0 For i = 0 To N-1 If L = 0 Then W = Z(i): L = 1 Elseif W = Z(i) Then L += 1 Else L -= 1 End If Next ' Sprawdzamy, czy mamy lidera If L = 0 Then t = 0 Else L = 0 For i = 0 To N-1 If W = Z(i) Then L += 1 Next t = (L > N\2) End If ' Wyświetlamy tablicę For i = 0 To N-1 If t And (Z(i) = W) Then Print Using " >##";Z(i); Else Print Using "####";Z(i); End If Next ' Wyświetlamy wyniki Print If t Then Print W;" : ";L Else Print "BRAK LIDERA" End If Print End |
Python
(dodatek)# Wyszukiwanie lidera # Data: 26.02.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- import random N = 80 Z = [] # Wypełniamy tablicę W = random.randrange(100) for i in range(N): if random.randrange(2): Z.append(random.randrange(100)) else: Z.append(W) # Wyszukujemy lidera L = 0 for i in range(N): if L == 0: W, L = Z[i], 1 elif W == Z[i]: L += 1 else: L -= 1 # Sprawdzamy, czy mamy lidera if L == 0: t = false else: L = 0 for i in range(N): if W == Z[i]: L += 1 t = (L > N//2) # Wyświetlamy tablicę for i in range(N): if t and (Z[i] == W): print(" >%2d" % Z[i], end="") else: print("%4d" % Z[i], end="") # Wyświetlamy wyniki print() if t: print(W,":",L) else: print("BRAK LIDERA") print() |
Wynik: |
74 9 72 72 72 39 20 72 98 54 71 90 72 47 73 72 72 72 72 58 92 36 72 23 79 36 72 72 15 90 13 72 97 72 72 76 91 87 72 62 42 72 82 95 72 51 72 74 72 72 98 72 72 72 30 72 94 92 28 72 72 20 74 72 43 7 72 52 85 72 38 2 72 72 72 72 72 29 5 49 BRAK LIDERA 33 52 41 >83 20 >83 >83 >83 >83 >83 >83 17 58 11 98 >83 87 >83 >83 71 57 >83 31 17 >83 >83 >83 >83 >83 >83 63 16 >83 46 >83 >83 >83 >83 41 61 41 68 98 >83 47 65 >83 >83 >83 >83 59 >83 >83 >83 23 >83 >83 >83 >83 >83 14 >83 70 10 >83 >83 >83 5 >83 >83 66 >83 >83 >83 53 91 >83 >83 2 >83 83 : 47 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.