Kim jest idol

Kim jest idol w zbiorze?

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba osób
znajomosci – tablica o wymiarach n × n; przechowuje liczby naturalne 0 oraz 1; tablica informacji na temat tego, które osoby się znają

Wynik:

komunikat wskazujący lidera zbioru lub informujący, że zbiór nie ma idola

Na przyjęciu znajduje się n osób. Osoby oznaczone są numerami od $0$ do $n - 1$ . Ponieważ jest to duża impreza, nie wszyscy goście się znają. Osoba A może znać osobę B, co niekoniecznie musi oznaczać, że osoba B zna osobę A. Może się okazać, że na przyjęciu pojawiła się osoba na tyle popularna, że jest znana przez wszystkich. Jeżeli ponadto okaże się, że osoba ta nie zna nikogo spośród pozostałych gości, możemy nazwać ją idolem.

Poniżej zaprezentowano dwuwymiarową tablicę typu logicznego, która określa stan znajomości wśród osób znajdujących się na przyjęciu. Jeżeli wartość znajomość[A][B] wynosi 1 (zauważmy, że to tablica liczb całkowitych, nie tablica boolowska), to przyjmujemy, że osoba A zna osobę B. Dla porządku przyjmujemy, że dana osoba nie zna siebie samej.

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

Polecenie 1

Czy na podstawie powyższej tablicy jesteś w stanie wskazać, która osoba jest idolem?

Zastanówmy się, ile pytań „Czy osoba A zna osobę B?” musimy zadać, aby sprawdzić, czy na przyjęciu pojawił się idol oraz kto nim jest.

Spróbujmy dokładnie przeanalizować informację, która wynika z odpowiedzi na pojedyncze pytanie: „Czy osoba A zna osobę B?” w kontekście wyszukiwania idola. Ponieważ idol jest osobą, która musi być znana przez każdego oraz sama nie może znać nikogo, wymienione wyżej pytanie pozwala nam stwierdzić, która z osób A lub B na pewno nie jest idolem. Jeżeli odpowiedź na nie brzmi twierdząco, wiemy, że osoba A nie może być idolem, ponieważ zna przynajmniej jedną osobę. Jeśli odpowiedź jest przecząca, to z kolei osoba B nie może być uznana za idola, ponieważ istnieje przynajmniej jedna osoba, która jej nie zna.

Tym sposobem możemy wyznaczyć idealnego kandydata na idola, zadając tylko $0$ do $n - 1$ pytań. Zapiszmy ten proces w postaci pseudokodu:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]
kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat = i

Następnie sprawdzimy, czy wyznaczony kandydat może być idolem. W tym celu musimy przepytać wszystkich gości, czy znają wyznaczonego kandydata, a także przepytać kandydata, czy nie zna nikogo. Każdy z tych procesów będzie składał się z zadania $n - 1$ pytań.

Do wcześniejszego pseudokodu dopiszemy linijki odpowiadające za sprawdzenie, czy wyznaczony kandydat jest idolem:

Linia 1. n ← 5. Linia 2. znajomość otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy ← otwórz nawias kwadratowy. Linia 3. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 8. zamknij nawias kwadratowy. Linia 10. kandydat ← 0. Linia 12. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 13. jeżeli znajomość otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy to. Linia 14. kandydat ← i. Linia 15. prawy ukośnik prawy ukośnik w przeciwnym wypadku kandydat dalej może być idolem. Linia 17. prawy ukośnik prawy ukośnik przepytaj gości przecinek czy znają kandydata. Linia 18. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 19. prawy ukośnik prawy ukośnik sprawdź czy osoba i nie jest kandydatem. Linia 20. jeżeli kandydat wykrzyknik znak równości i to. Linia 21. prawy ukośnik prawy ukośnik sprawdź przecinek czy osoba i zna kandydata. Linia 22. jeżeli wykrzyknik znajomość otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy to. Linia 23. prawy ukośnik prawy ukośnik osoba i nie zna kandydata. Linia 24. prawy ukośnik prawy ukośnik kandydat nie jest idolem. Linia 25. prawy ukośnik prawy ukośnik idol nie istnieje. Linia 26. wypisz cudzysłów Idol nie istnieje cudzysłów. Linia 27. zakończ działanie pętli. Linia 29. prawy ukośnik prawy ukośnik przepytaj kandydata przecinek czy nie zna gości. Linia 30. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 31. prawy ukośnik prawy ukośnik sprawdź przecinek czy kandydat nie jest osobą i. Linia 32. jeżeli kandydat wykrzyknik znak równości i to. Linia 33. prawy ukośnik prawy ukośnik sprawdź przecinek czy kandydat nie zna osoby i. Linia 34. jeżeli znajomość otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy to. Linia 35. prawy ukośnik prawy ukośnik kandydat zna osobę i. Linia 36. prawy ukośnik prawy ukośnik kandydat nie jest idolem. Linia 37. prawy ukośnik prawy ukośnik idol nie istnieje. Linia 38. wypisz cudzysłów Idol nie istnieje cudzysłów. Linia 39. zakończ wykonywanie programu. Linia 41. wypisz cudzysłów Idolem jest osoba numer cudzysłów plus kandydat.

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// przepytaj gości, czy znają kandydata
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy osoba i nie jest kandydatem
	jeżeli kandydat != i to
    	// sprawdź, czy osoba i zna kandydata
    	jeżeli !znajomość[i][kandydat] to
        	// osoba i nie zna kandydata
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ działanie pętli

// przepytaj kandydata, czy nie zna gości
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź, czy kandydat nie jest osobą i
	jeżeli kandydat != i to
        // sprawdź, czy kandydat nie zna osoby i
    	jeżeli znajomość[kandydat][i] to
        	// kandydat zna osobę i
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Powyższy kod można skrócić, wykorzystując podobieństwo dwóch pętli:

Linia 1. n ← 5. Linia 2. znajomość otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy ← otwórz nawias kwadratowy. Linia 3. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 8. zamknij nawias kwadratowy. Linia 10. kandydat ← 0. Linia 12. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 13. jeżeli znajomość otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy to. Linia 14. kandydat ← i. Linia 15. prawy ukośnik prawy ukośnik w przeciwnym wypadku kandydat dalej może być idolem. Linia 17. prawy ukośnik prawy ukośnik sprawdź przecinek czy kandydat jest idolem. Linia 18. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 19. prawy ukośnik prawy ukośnik sprawdź czy nie pytamy kandydata o samego siebie. Linia 20. prawy ukośnik prawy ukośnik oraz czy czy osoba i zna kandydata. Linia 21. prawy ukośnik prawy ukośnik oraz czy kandydat nie zna osoby i. Linia 22. jeżeli kandydat wykrzyknik znak równości i. Linia 23. oraz wykrzyknik znajomość otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy. Linia 24. oraz znajomość otwórz nawias kwadratowy kandydat zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy to. Linia 25. prawy ukośnik prawy ukośnik osoba i nie zna kandydata. Linia 26. prawy ukośnik prawy ukośnik lub kandydat zna osobę i. Linia 27. prawy ukośnik prawy ukośnik kandydat nie jest idolem. Linia 28. prawy ukośnik prawy ukośnik idol nie istnieje. Linia 29. wypisz cudzysłów Idol nie istnieje cudzysłów. Linia 30. zakończ wykonywanie programu. Linia 32. wypisz cudzysłów Idolem jest osoba numer cudzysłów plus kandydat.

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// sprawdź, czy kandydat jest idolem
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy nie pytamy kandydata o samego siebie
    // oraz czy czy osoba i zna kandydata
    // oraz czy kandydat nie zna osoby i
	jeżeli kandydat != i
    	oraz !znajomość[i][kandydat]
        oraz znajomość[kandydat][i] to
        // osoba i nie zna kandydata
        // lub kandydat zna osobę i
        // kandydat nie jest idolem
        // idol nie istnieje
        wypisz "Idol nie istnieje"
        zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Przedstawiony algorytm pozwala nam na znalezienie idola po zadaniu $3 (n - 1)$ pytań.

By to uzasadnić, przypomnijmy jak działa omówiony algorytm. Najpierw sprawdzamy, czy każda kolejna osoba (poza pierwszą) zna obecnego kandydata (czyli pierwszą osobę). Daje to $n - 1$ pytań.

Następny krok wymaga sprawdzana, czy kolejne osoby z grupy znają kandydata (czyli znowu zadajemy $n - 1$ pytań) oraz czy kandydat zna te kolejne osoby (kolejne $n - 1$ pytań).

By znaleźć idola zadajemy $3 (n - 1)$ pytań. To oznacza, że złożoność czasowa omówionego algorytmu wynosi $O (n)$ .

Wyszukiwanie binarne - implementacja algorytmu

Lider w zbiorze

Kim jest idol w zbiorze?