Jeśli przedstawimy w postaci dwójkowej: to, wiedząc, że otrzymamy:
Ostatni krok wynika z tego, że a .
Implementacja Przykładowa implementacja powyższego rozwiązania w języku Python 3: def flawiusz(n): # Wyznaczenie l l = n - (1 << (n.bit_length() - 1))
# Wyznaczenie miejsca bezpiecznego z wzoru (3) wynik = 2*l + 1 return wynik
Przypadek ogólny Problemem, który pozostaje otwarty, jest wyznaczanie w sytuacji, gdy Rozwiązanie intuicyjne, działające w złożoności polega na wykorzystaniu listy i przechodzeniu jej w koło, usuwając co -ty odwiedzony element. Opisano też rozwiązania, działające w i wykorzystujące zamiast listy binarne drzewa poszukiwań.
Szybsze rozwiązanie, działające w złożoności przewiduje wykorzystanie programowania dynamicznego. Niech oznacza pozycję bezpieczną przy wybranym Jeżeli numerujemy, zaczynając od to osoba o pozycji od niej znajduje się na pozycji Gdy zabijemy osobę na -tej pozycji, zostajemy z kręgiem złożonym z osób i zaczynamy odliczać od osoby, która w oryginalnym problemie stała na pozycji Biorąc pod uwagę zmianę numeracji w nowym kręgu, otrzymujemy następującą rekurencję:
Przypisy
Linki zewnętrzne
Symulacja problemu na cut-the-knot.org
Kategoria:Kombinatoryka