Josephus-Problem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Josephus-Problem oder die Josephus-Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik.

Es werden nummerierte Objekte im Kreis angeordnet; dann wird, beginnend mit der Nummer , jedes -te Objekt entfernt, wobei der Kreis immer wieder geschlossen wird. Die Reihenfolge der entfernten Objekte wird als Josephus-Permutation bezeichnet.

Ziel dieses Problems ist es, bei gegebenem und , das letzte Objekt der Permutation zu bestimmen.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Das Problem wurde nach dem jüdischen Historiker Flavius Josephus benannt, welcher sich 67 n. Chr. beim Kampf um die galiläische Stadt Jotapata mit 40 weiteren Männern in einer Höhle vor den Römern versteckt hielt. Als das Versteck verraten wurde, sicherten die Römer Josephus freies Geleit zu für den Fall, dass er das Versteck verließ. Seine Gefolgsleute drohten allerdings ihn umzubringen und wollten lieber sterben, als den Römern in die Hände zu fallen. Daraufhin machte Josephus den Vorschlag eines kollektiven Suizids, in dem sich alle im Kreis aufstellen und jeder seinen linken Nachbarn töten sollte. Er stellte sich an die 19. Stelle, blieb damit als Letzter übrig und ergab sich den Römern und überlebte.

Lösung[Bearbeiten | Quelltext bearbeiten]

Das Problem wird hier gelöst für den Fall, dass jedes 2. Element entfernt wird (). Für den allgemeinen Fall folgt eine Lösung unten. Die Lösung wird mittels Rekursion hergeleitet. bezeichne das letzte Element der Permutation, wenn anfangs Elemente vorhanden waren (mit ). Im ersten Durchlauf werden alle geradzahligen Elemente entfernt. In der zweiten Runde werden die Elemente entfernt, die an der neuen 2., 4. usw. Position stehen, so als hätte es keine erste Runde gegeben. Wenn die Anfangsanzahl von Elementen gerade ist, dann war das Element aus der zweiten Runde in der ersten Runde an Position . Das Element war ursprünglich auf Position . Das ergibt folgende Rekursionsformel:

Wenn die Elementanzahl anfangs ungerade ist, dann wird in der zweiten Runde das ursprünglich erste Element entfernt, aber auch hier wird dann das neue 2., 4. usw. Element entfernt. In diesem Fall ergibt sich, dass Element in der ersten Runde an Position war. Daraus folgt die Rekursionsformel:

Wenn man die Werte für und tabellarisch darstellt sieht man ein Muster:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Diese Tabelle lässt vermuten, dass eine aufsteigende Folge ungerader Zahlen ist, welche wieder mit startet, wenn der Index eine Zweierpotenz ist. Wenn man und so wählt, dass und , dann folgt . Es ist offensichtlich, dass die Werte aus der Tabelle diese Gleichung erfüllen. Nachfolgend erfolgt der Beweis durch vollständige Induktion.

Behauptung: Wenn und , dann folgt .

Beweis: Vollständige Induktion über . Der Fall ist wahr. Man betrachte die Fälle für gerades und ungerades getrennt.

Wenn gerade, dann wähle man und so, dass und . Es gilt . Wir haben , bei der die zweite Gleichung aus der Induktionsannahme folgt.

Wenn ungerade, dann wähle man und so, dass and . Es gilt . Wir haben , bei der die zweite Gleichung ebenfalls aus der Induktionsannahme folgt. Damit ist die Behauptung bewiesen.

Die eleganteste Form der Lösung folgt aus der binären Repräsentation von : kann durch eine 1-Bit-Linksrotation von selbst ermittelt werden. Wenn man binär als repräsentiert, dann ist die Lösung gegeben als . Der Beweis folgt aus der Repräsentation von als .

Die dynamische Programmierung ist der einfachste Weg dieses Problem für den allgemeinen Fall zu lösen.

Diese Methode verwendet die Rekursionsformel:

, mit

welche offensichtlich ist, wenn man berücksichtigt, wie sich die Nummer des letzten Elements ändert wenn man von nach wechselt. Diese Methode hat eine Laufzeit von , aber für kleine und große gibt es einen anderen Ansatz. Dieser zweite Ansatz verwendet auch die dynamische Programmierung, erfordert aber nur eine Laufzeit von . Er entfernt die k., 2k., ..., . Elemente in einem Schritt und ändert dann die Nummerierung.

Implementierung[Bearbeiten | Quelltext bearbeiten]

Der folgende Algorithmus realisiert das Problem rekursiv nach der obigen Rekursionsformel für den Fall k=2 und besitzt eine Laufzeit von O(log(n)).

int josephus(int n) 
{
    if(n == 1) 
        return 1;

    if((n%2) == 0) 
        return 2 * josephus(n / 2) - 1;

    if((n%2) == 1) 
        return 2 * josephus((n - 1) / 2) + 1;
}

Gemäß der geschlossenen Formel f(n)=2*l + 1 lässt sich der folgende nicht-rekursive Algorithmus angeben. Seine Laufzeit liegt in O(1).

int josephus(int n)
{
    m = floor( log(n) );
    l = n - 2^m;
    j = 2*l + 1;

    return j;
} 

Literatur[Bearbeiten | Quelltext bearbeiten]