Przeczytaj

Implementacja algorytmów w języku Java

Wiesz już, czym są liderliderlider oraz idolidolidol.

Jak jednak zaimplementować algorytm wyszukiwania idola i lidera w języku Java?

R1bsiotbB0oo61

Ćwiczenie 1

Algorytm znajdowania lidera wykorzystywany jest w Polsce podczas wyborów prezydenckich (jeśli jednak w pierwszej turze nie zostaje wybrany lider, następuje druga tura wyborów). W pewnej szkole przeprowadzono wybory przewodniczącego samorządu uczniowskiego, wykorzystując ten sam model. Napisz program, który wykorzysta algorytm znajdowania lidera do wyłonienia nowego przewodniczącego samorządu uczniowskiego.

Przetestuj działanie programu dla następujących wyników, zawierających n = 105 głosów:

Linia 1. oddaneGlosy znak równości otwórz nawias klamrowy cudzysłów DD cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 2. cudzysłów CC cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek. Linia 3. cudzysłów CC cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów CC cudzysłów przecinek. Linia 4. cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 5. cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek. Linia 6. cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 7. cudzysłów AA cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 8. cudzysłów CC cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek. Linia 9. cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 10. cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów AA cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów przecinek. Linia 11. cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów BB cudzysłów przecinek. Linia 12. cudzysłów DD cudzysłów przecinek cudzysłów CC cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów DD cudzysłów przecinek cudzysłów BB cudzysłów przecinek cudzysłów CC cudzysłów zamknij nawias klamrowy średnik.

oddaneGlosy = {"DD", "AA", "DD", "BB", "DD", "BB", "BB",
"CC", "CC", "DD", "DD", "CC", "BB", "DD", "DD", "CC",
"CC", "BB", "CC", "CC", "DD", "DD", "BB", "CC", "CC",
"BB", "CC", "DD", "DD", "BB", "BB", "BB", "CC", "BB",
"BB", "BB", "BB", "BB", "AA", "CC", "AA", "BB", "DD",
"CC", "DD", "AA", "DD", "DD", "BB", "BB", "DD", "BB",
"AA", "BB", "DD", "DD", "DD", "BB", "BB", "DD", "BB",
"CC", "BB", "DD", "AA", "AA", "DD", "DD", "CC", "DD",
"BB", "CC", "DD", "DD", "BB", "DD", "BB", "DD", "BB",
"DD", "DD", "CC", "CC", "DD", "AA", "CC", "BB", "CC",
"DD", "CC", "DD", "DD", "DD", "BB", "BB", "BB", "BB",
"DD", "CC", "DD", "DD", "DD", "DD", "BB", "CC"};

gdzie:

AA – Adam Angielski
BB – Bartosz Brytyjski
CC – Celina Chińska
DD – Damian Duński

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba oddanych głosów
oddaneGlosy – n-elementowy zbiór głosów oddanych na poszczególnych kandydatów; zbiór łańcuchów znaków

Wynik:

Na standardowym wyjściu wyświetlane są imię i nazwisko lidera w zbiorze oddaneGlosy, jeśli lider istnieje; w przeciwnym wypadku należy wyświetlić komunikat „Brak lidera”.

R1e9TxWdihC4F

Ćwiczenie 2

Napisz program znajdujący idola w zbiorze n osób na podstawie tablicy znajomości. Osoby numerowane są od 0 do n - 1. Przetestuj poprawność rozwiązania dla n = 4 osób oraz następującej tablicy znajomości:

tablicaZnajomosci = {
	{false, true, true, false},
	{false, false, true, false},
	{false, false, false, false},
	{true, true, true, false}
};

Specyfikacja problemu:

Dane:

n – liczba naturalna większa od 1
tablicaZnajomosci[i][j] – tablica wartości logicznych; zawiera informację o tym, czy osoba o numerze i zna osobę o numerze j; przy założeniu, że: j, i < n

Wynik:

Na standardowym wyjściu wyświetlany jest komunikat „Idolem jest osoba numer X”, jeśli idol istnieje w danym zbiorze n osób, lub „Idol nie istnieje” w przeciwnym wypadku.

RbGPn2CT8XG50

Słownik

idol

w grupie n osób idolem nazywamy osobę, która znana jest przez każdą z pozostałych n - 1 osób, natomiast sama nie zna nikogo

lider

element n‑elementowego zbioru, który występuje w nim więcej niż $\frac{n}{2}$ razy

Film samouczek

Sprawdź się

Implementacja algorytmów w języku Java

Słownik