Beschreibung: In einem Kreis stehen Menschen, die darauf warten, hingerichtet zu werden. Das Auszählen beginnt irgendwann im Kreis und läuft in einer festen Richtung um den Kreis herum. In jedem Schritt wird eine bestimmte Anzahl von Personen übersprungen und die nächste Person ausgeführt. Die Beseitigung erfolgt um den Kreis (der immer kleiner wird, wenn die hingerichteten Personen entfernt werden), bis nur noch die letzte Person übrig bleibt, der die Freiheit gegeben wird.

Ich habe dieses "Josephus-Problem" gegoogelt und der Wikipedia-Hit gibt mir eine dynamische Programmierlösung:f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, aber dies ergibt nur den letzten Überlebenden. Wie kann ich die Reihenfolge der Personen ausführen lassen? Angenommen, p (5, 3) = {3,1,5,2,4}.

Auch gibt es eineO(nlogn) Lösung anstelle von aO(nk) ein?