Strona główna » Po Godzinach » Zagadki » Ostatni w Kółku
 

Ostatni w Kółku

https://mattomatti.com/a0061

Zadanie

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?

Odpowiedź

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ągCo usuwamy?
1, 2, 3, .., 1001, 3, 5, .., 99 (nieparzyste)
2, 4, 6, .., 1002, 6, 10, .., 98 (indeksy nieparzyste)
4, 8, 12, .., 1004, 12, 20, .., 100 (indeksy nieparzyste)
8, 16, 24, .., 9616, 32, 48, 64, 80, 96 (indeksy parzyste)
8, 24, 40, 56, 72, 8824, 56, 88
8, 40, 7240
8, 728
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.

Implementacja

Zadanie

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.

Rozwiązanie

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.

C++
C#
  1. int ktoreDziecko(int n, int k) {
  2.   vector<int> v;
  3.   for (int i = 1; i <= n; i++)
  4.     v.push_back(i);
  5.   int o = 0;
  6.   while (v.size() > 1) {
  7.     v.erase(v.begin() + o);
  8.     o = (o + k - 1) % v.size();
  9.   }
  10.   return v[0];
  11. }

W celu uproszczenia zarządzania, które numery pozostały to został zastosowany wektor, który (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 wektor 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 wektora.

Testowanie funkcji

Poniższy fragment kodu wczyta od użytkownika potrzebne dane do obliczeń, a następnie wypisze wynik.

C++
C#
  1. int main() {
  2.   int n, k;
  3.   cout << "Podaj ile jest dzieci w kolku\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj ile osob dalej podawana jest pilka\n k = ";
  6.   cin >> k;
  7.   cout << "Ostatnie dziecko bedzie miec numer ";
  8.   cout << ktoreDziecko(n, k);
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

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.