Mi. Nov 6th, 2024

Der Legende von Josephus nach, trieben die Römer eine Gruppe von Kriegern in eine Höhle, um diese dann gefangen zu nehmen. Nach der Legende entschieden diese Krieger aber dann sich nicht gefangen nehmen zu lassen, sondern lieber den Heldentod zu sterben d.h. sich gegenseitig umzubringen. In dem jeder seinen nächsten in der Reihe töten sollte. Also der Erste tötet den Zweiten, der Dritte den Vierten usw.
Nun stellt sich natürlich die Frage, sind alle Positionen gleich gut oder gibt es eine günstigste Position?

Um diese Frage zu beleuchten, formulieren wir das Problem etwas weniger kriegerisch um: Dazu stellen uns eine Menge n mit Personen vor, die in einer Reihe stehen und definieren zwei Funktionen:
RotateLeft: Nimmt die erste Person in der Reihe und stellt diese ans Ende der Reihe
Rest: Entfernt die nächste Person in der Reihe

Der Ablauf sieht nun wie folgt aus: Wir starten mit dem Aufruf der Funktion RotateLeft, diese nimmt die erste Person nach dem diese seinen Nachfolger virtuell erschlagen hat von der Liste und setzt sie am Ende ein. Dann folgt der Aufruf der Funktion Rest, diese eliminiert die zweite Person aus der Liste. Dann folgt wieder die Funktion RotateLeft, gefolgt von Rest usw. Dieser Prozess läuft solange bis nur noch eine Person übrig ist.

Mit Hilfe von Mathematica lässt sich dieser Ablauf sehr anschaulich programmieren und nachvollziehbar darstellen. Wir schreiben dazu eine rekursive Funktion mit dem Namen survivor[liste]. Dieser Funktion übergeben wir immer wieder die aktualisierte Liste der Personen.

Survivor[liste_] := 
 Nest[(Rest[RotateLeft[#]]) &, liste, Length[liste] - 1]

Mit Hilfe der Trace-Funktion die wir auf die RotateLeft Funktion anwenden, wird der rekursive Programm-Ablauf deutlicher:

TracePrint[Survivor[Range[20]], RotateLeft]

    RotateLeft
   {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1}
    RotateLeft
   {4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,3}
    RotateLeft
   {6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,3,5}
    RotateLeft
   {8,9,10,11,12,13,14,15,16,17,18,19,20,1,3,5,7}
    RotateLeft
   {10,11,12,13,14,15,16,17,18,19,20,1,3,5,7,9}
    RotateLeft
   {12,13,14,15,16,17,18,19,20,1,3,5,7,9,11}
    RotateLeft
   {14,15,16,17,18,19,20,1,3,5,7,9,11,13}
    RotateLeft
   {16,17,18,19,20,1,3,5,7,9,11,13,15}
    RotateLeft
   {18,19,20,1,3,5,7,9,11,13,15,17}
    RotateLeft
   {20,1,3,5,7,9,11,13,15,17,19}
    RotateLeft
   {3,5,7,9,11,13,15,17,19,1}
    RotateLeft
   {7,9,11,13,15,17,19,1,5}
    RotateLeft
   {11,13,15,17,19,1,5,9}
    RotateLeft
   {15,17,19,1,5,9,13}
    RotateLeft
   {19,1,5,9,13,17}
    RotateLeft
   {5,9,13,17,1}
    RotateLeft
   {13,17,1,9}
    RotateLeft
   {1,9,17}
    RotateLeft
   {17,9}
  RotateLeft
   {9}

An diesem Beispiel wird deutlich, was für ein mächtiges Werkzeug Mathematica ist, um sehr komplexe Fragestellungen zu untersuchen.