W kółku stoi 100 dzieci, którym przypisano kolejne liczby 1, 2, .., 100. Zabawa polega na rzucaniu piłki do osoby ustawionej w kółku dwie osoby dalej. Każdy kto dotknie piłki rzuca piłkę dalej i opuszcza kółko. Grę rozpoczyna dziecko z numerem 1. Ostatnie dziecko w kółku wygrywa, który numer wygra?
Ostatnie dziecko, które nie odpadło będzie mieć numer 72.
Jednym ze sposobów do rozwiązania tego zadania jest wypisanie wszystkich liczb, a następnie skreślenie pierwszenie, a potem co drugą, ale sam proces wypisywania jest bardzo czasochłonny i można łatwo się pomylić. W celu uproszczenia zadania należy zauważyć pewne prawidłowości.
Po pierwsze piłkę początkowo trzyma dziecko o numerze 1. Po otrzymaniu piłki rzuca do dziecka o numerze 3 i opuszcza koło. W ten sposób z koła zostaną wyeliminowane wszystkie numery nieparzyste. Potem można pozostałe numery zindeksować wartościami od 1 i ponownie usunąć wszystkie indeksy nieparzyste o ile ciąg poprzednim razem miał parzystą liczbę elementów. W przeciwnym wypadku usuwamy indeksy parzyste Powtarzając ten proces dojdziemy do momentu, gdy zostanie tylko jedna wartość. Metode tą obrazuje poniższa tabelka:
Aktualny Ciąg | Co usuwamy? |
---|---|
1, 2, 3, .., 100 | 1, 3, 5, .., 99 (nieparzyste) |
2, 4, 6, .., 100 | 2, 6, 10, .., 98 (indeksy nieparzyste) |
4, 8, 12, .., 100 | 4, 12, 20, .., 100 (indeksy nieparzyste) |
8, 16, 24, .., 96 | 16, 32, 48, 64, 80, 96 (indeksy parzyste) |
8, 24, 40, 56, 72, 88 | 24, 56, 88 |
8, 40, 72 | 40 |
8, 72 | 8 |
72 | - |
W całym procesie należy bardzo uważnie śledzić ile elementów w ciągu pozostało i odpowiednio zmienić, które indeksy zostaną usunięte.
Napisz program, który wczyta liczbę n wszystkich dzieci stojących w kółku oraz jak daleko rzucają dzieci tj. k osób dalej. Wynikiem działania funkcji powinien być numer dziecka, które zostanie jako ostatnie w kole.
Obliczenia związane z wyszukiwaniem numeru dziecka, które zostanie jako ostatnie w kółku będzie przeprowadzać funkcja ktoreDziecko(), która przyjmie dwa argumenty: n - ile jest dzieci w kółku oraz k - ile dzieci dalej jest rzucana piłka.
W celu uproszczenia zarządzania, które numery pozostały to została zastosowana lista, która (3. - 4.) na początku przechowuje wszystkie numery dzieci. Potem (5.) deklarujemy zmienną o, która będzie wskazywać osobę, która aktualnie trzyma piłkę. Potem (6.) dopóki lista będzie mieć więcej niż jeden element to: (7.) usuń osobę, która aktualnie posiada piłkę i (8.) przekaż piłkę dalej. Tutaj od sumy aktualnego numeru i zasięgu rzutu odejmujemy jeden, ponieważ usunęliśmy już z listy osobę, która trzymała w tej iteracji piłkę. na koniec (10.) zwracamy pierwszy i zaraz ostatni element listy.
Poniższy fragment kodu wczyta od użytkownika potrzebne dane do obliczeń, a następnie wypisze wynik.
Napisz program, który wczyta ilość n dzieci w kółku, zasięg rzutu k oraz numer osoby p, która trzyma na początku piłkę. Tym razem dzieci rzucają piłką przeciwnie do ruchu wskazówek zegara tj. nie w stronę rosnących numerów. Program powinien zwrócić numer dziecka, które zostanie jako ostatnie.
Przykładowo jeśli w kółku stoi 5 dzieci i przerzucają piłkę dwie osoby do tyłu, a jako pierwsze trzyma piłkę dziecko o numerze 4 to poprawnym wynikiem jest 3. Wyjaśnienie - kolejno piłkę otrzymują dzieci o numerach: 4, 2, 5, 1 i 3.