problem Flawiusza Josephusa

//Zaprogramuj, z użyciem jednokierunkowej listy cyklicznej (w której następnikiem „ostatniego”
elementu jest „pierwszy” element listy), tzw. problem Flawiusza Josephusa.
Objaśnienie:
Flawiusz Josephus był historykiem żyjącym w I w. Legenda głosi, że gdyby nie jego talent matematyczny,
nie dożyłby chwili gdy został sławny. W czasie wojny żydowsko-rzymskiej był on w
oddziale 41 (czyli „N”) żydowskich buntowników osaczonych przez Rzymian. Woląc śmierć od
niewoli, buntownicy stanęli w kole, odliczając i zabijając co trzecią (co „K-tą”) osobę. Jednak
Flawiusz, wraz ze swym przyjacielem, chcieli uniknąć takiej śmierci. Flawiusz szybko obliczył
gdzie powinni obaj stanąć, aby byli ostatnimi dwiema osobami, które zostaną przy życiu.

Program powinien więc, dla zadanych dwóch liczb: N oraz K (jak w objaśnieniu), wyznaczyć
początkową pozycję dwóch elementów listy, które pozostaną w powtarzanym cyklicznie procesie
usuwania co K-tego elementu listy N-elementowej, rozpoczynając od 1. elementu (pierwszy
usuwany element ma numer: (K-1) mod N +1 ). Należy też wyświetlić kolejne usuwane elementy
listy.//

Listę już wykonałem, elementy są odejmowane i zostają 2, lecz nie mam algorytmu jak z marszu obliczyć, które 2 miejsca zostaną jako ostatnie. W necie jest problem rozwiązany, ale tylko dla wskazania ostatniego elementu, a nie 2.
Byłbym wdzięczny za algorytm/funkcję:

Wejście:
N - liczba ludzi (stoją tak jakby w kręgu)
K - co który jest usuwany

Zaczynamy zabijać ludka stojącego na pozycji **(K-1) mod N +1 ** (Wydaje mi się czy zawsze z tego wyjdzie K?)

Wyjście:
A,B - numery 2 ludków, którzy zostaną jako ostatni przy życiu.

Pewnie to z 5 linijek kodu, ale nie daję rady, prawie całe zadanie zrobione tylko tego mi brakuje.
(może być w pseudokodzie, C++, Pascal).

Ręcznie potrafię wyznaczyć, ale wzoru na to chyba nie ma. No chyba, że ktoś sprytny go utworzy.

Ciekawy problem, zobaczymy czy ktoś go rozwiąże.

Zaczynamy zabijać ludka stojącego na pozycji (K-1) mod N +1 (Wydaje mi się czy zawsze z tego wyjdzie K?)

Wydaje Ci się. K może być bardzo duże, znacznie większe od N.

Ja chyba znam rozwiązanie ale to będzie trochę więcej linijek kodu niż 5... :]
Do tego reguły nie są do końca jasne - musiałem przyjąć kilka założeń, które nie wynikają wprost z tego zadania...
Powodzenia!

Aha i pamiętaj, że oni stoją w kółku więc nie ważne ilu zabijesz tj. nie ważne jakie jest K i N odliczać możesz bez końca -> dlatego może być, że K >>> N

Załóżmy więc, że K jest mniejsze od N.

Już nawet coś rekurencyjnie ostatecznie może być...

Jeżeli (jak piszesz) masz program, który pozostawia dwóch żywych i wypisuje kolejnych zabijanych, to go trochę przedłuż, tak by nikt nie został żywy. Dwaj ostatni zabici stanowią rozwiązanie.

Mój program tak działa. Zrobiłem kolekcję jaką jest lista wiązana jednokierunkowa cykliczna i usuwam co K tego aż dwóch zostaje. Ale Flawiusz nie mógł czekać, aż wszystkich zabiją, tylko wcześniej sprytnie jako matematyk obliczył te miejsca.

Można rysować f-kcję kwadratową i wtedy odczytać gdzie są miejsca zerowa, ale jest też wzór, który nam to z miejsca liczy dla a,b,c, a ja chcę wzrór na problem Flawiusza dla K i N oraz 2 wyniki.

Skąd Ty wiesz jak Flawiusz to wyliczył? Przecież to żaden problem wykonać odpowiedni program w głowie.

Widzę, że nie ma nikogo bystrego na tym forum kto by jakiś wzór podał.

Miło, że tak wysoko cenisz forum. Gdybym znalazł wzór, to bym publikował pracę w czasopismach matematycznych. Jawny wzór jest znany dla k=2, ostatni zabijany jest na pozycji 1+2n-2^{(1+floor(log(n))},
Logarytm jest przy podstawie 2.

Użyj jakiegoś drzewa zrównoważonego, np drzewo rozchylane. W węzłach trzymaj rozmiar poddrzewa z korzeniem w tym węźle oraz numer Żyda. Usuwanie węzła będzie wtedy trwało O(lg n), w sumie masz do usunięcia O(n) węzłów, więc czas algorytmu wyniesie O(n lg n).

Ewentualnie na Wikipedii jest opisane rozwiązanie działające w czasie O(k lg n), które jest lepsze o ile jest k < n.

Wkurzyłem się i sam dałem radę algorytm znaleźć, przydała się tylko duża doza pomysłu od kolegi, który lubi się bawić matmą dyskretną/logiką.

Wystarczyło dużo pomyśleć, pokombinować i rozwiązanie się znalazło. Mam coś jakby wzór, a nie zabawę na drzewach jak ktoś proponował, czy obliczanie poprzez usuwanie elementów, po prostu 12 linijek kodu. 3 pętle, parę ifów, 6 zmiennych, bez żadnych tablic, list(i innych kolekcji).

Nie jestem w takich rzeczach biegły, ale dałem radę. Myślałem, że takim mózgom jak wam zajmie to 15min., ale widać szpanować tylko potraficie i matmę, algorytmikę i logiczne myślenie macie głęboko w poważaniu.

Nie wiem czy pamiętasz, ale Ty chciałeś dostać wzór (nie program, nie algorytm). Teraz piszesz, że Ci kolega napisał program i to Ci wystarcza. Program to ja napisałem w 10 minut (dla dowolnego n i k). Natomiast wzoru nie znalazłem. Jeśli Ty go masz, to go zdradź.

bo mógłbyś dla mnie wrzucić ten program, który napisałeś na forum? Byłabym Ci bardzo wdzięczna :)