Przeczytaj

Implementacja algorytmu znajdowania lidera w C++

Liderem nazywamy liczbę, która występuje w zbiorze o długości n więcej niż $\frac{n}{2}$ razy. Ponieważ inna liczba nie może występować w tym samym zbiorze liczbowym więcej niż $\frac{n}{2}$ razy, lider jest tylko jeden. W zbiorze {1, 4, 6, 1, 1} lider to zatem liczba 1, ponieważ występuje w nim aż 3 razy.

W implementacji algorytmu znajdowania lidera użyjemy dodatkowej zmiennej dlugoscZbioru, która będzie zawierać liczbę elementów tablicy.

int zbior[3] = {1, 3, 1};
int dlugoscZbioru = 3;
int lider = zbior[0];
int n = 1;

Następnie zaimplementujemy pętlę for, wraz ze wszystkimi instrukcjami warunkowymiinstrukcja warunkowainstrukcjami warunkowymi, które są potrzebne, aby algorytm zadziałał.

int zbior[3] = {1, 3, 1};
int dlugoscZbioru = 3;
int lider = zbior[0];
int n = 1;

for (int i = 1; i < dlugoscZbioru; i++) {
	if (n > 0) {
		if (lider == zbior[i]) {
			n = n + 1;
		} else {
			n = n - 1;
		}
	} else {
		lider = zbior[i];
		n = 1;
	}
}

Kolejnym krokiem jest sprawdzenie, czy wartość zmiennej n wynosi 0. Jeżeli tak, możemy zakończyć działanie programu, ponieważ zbiór na pewno nie ma lidera. Jeżeli nie, wartość znajdująca się w zmiennej lider jest potencjalnym liderem.

int zbior[3] = {1, 3, 1};
int dlugoscZbioru = 3;
int lider = zbior[0];
int n = 1;

for (int i = 1; i < dlugoscZbioru; i++) {
	if (n > 0) {
		if (lider == zbior[i]) {
			n = n + 1;
		} else {
			n = n - 1;
		}
	} else {
		lider = zbior[i];
		n = 1;
	}
}

if (n == 0) {
	cout << "Zbiór nie ma lidera" << endl;
	return 0;
}

Ostatnim krokiem jest sprawdzenie, ile razy potencjalny kandydat wytypowany przez algorytm występuje w zbiorze. Jeżeli liczba ta jest większa niż długość zbioru podzielona przez 2, liczba ta jest liderem tego zbioru.

Linia 1. using namespace std średnik. Linia 3. int zbior otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 3 przecinek 1 zamknij nawias klamrowy średnik. Linia 4. int dlugoscZbioru znak równości 3 średnik. Linia 5. int lider znak równości zbior otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 6. int n znak równości 1 średnik. Linia 8. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny dlugoscZbioru średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły n zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. if otwórz nawias okrągły lider znak równości znak równości zbior otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. n znak równości n plus 1 średnik. Linia 12. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 13. n znak równości n minus 1 średnik. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 16. lider znak równości zbior otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 17. n znak równości 1 średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. if otwórz nawias okrągły n znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zbiór nie ma lidera cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 23. return 0 średnik. Linia 24. zamknij nawias klamrowy. Linia 26. int liczbaWystapienLidera znak równości 0 średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dlugoscZbioru średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły zbior otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości lider zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. liczbaWystapienLidera plus znak równości 1 średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 33. if otwórz nawias okrągły liczbaWystapienLidera zamknij nawias ostrokątny dlugoscZbioru prawy ukośnik 2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liderem zbioru jest cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny lider otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 35. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 36. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Zbiór nie ma lidera cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 37. zamknij nawias klamrowy.

using namespace std;

int zbior[3] = {1, 3, 1};
int dlugoscZbioru = 3;
int lider = zbior[0];
int n = 1;

for (int i = 1; i < dlugoscZbioru; i++) {
	if (n > 0) {
		if (lider == zbior[i]) {
			n = n + 1;
		} else {
			n = n - 1;
		}
	} else {
		lider = zbior[i];
		n = 1;
	}
}

if (n == 0) {
	cout << "Zbiór nie ma lidera" << endl;
	return 0;
}

int liczbaWystapienLidera = 0;
for (int i = 0; i < dlugoscZbioru; i++) {
	if (zbior[i] == lider) {
	liczbaWystapienLidera += 1;
	}
}
    
if (liczbaWystapienLidera > dlugoscZbioru / 2) {
	cout << "Liderem zbioru jest " << lider << endl;
} else {
	cout << "Zbiór nie ma lidera" << endl;
}

Słownik

instrukcja warunkowa

element algorytmu pozwalający na sprawdzenie jednego lub kilku warunków, a następnie zdefiniowanie, jakie czynności mają być wykonane, jeśli dane warunki są spełnione lub niespełnione (służy do sterowania programem)

inicjalizacja

nadanie wartości początkowej

Wprowadzenie

Symulacja interaktywna

Implementacja algorytmu znajdowania lidera w C++

Słownik