Das Josephus-Problem ist eine alte Denkaufgabe: Eine Anzahl Gefangene (z.B. 41) wird in einem Kreis aufgestellt und dann wird abgezählt: Immer nach einer bestimmten Zahl, z.B. immer beim Dritten, wird der Kopf abgeschlagen. Dies geht so lange im Kreis der noch Verbliebenen herum, bis nur noch einer übrig bleibt. Die Frage ist nun, wo muss ich mich hinstellen, damit ich als Letzte überlebe?
Es gibt unzählige Lösungen für dieses Problem in diversen Programmiersprachen, hier ist meine Lösung in Groovy:
k = 3 //Immer der k. wird geköpft
n = 41 //Anzahl Gefangene
//Alle Gefangenen im Kreis, true = lebt, false = tot
kreis = [true] * n //Array mit n boolschen Werten
println kreis
pos = -1
anzFalse = 0
//die Schleife läuft, solange es noch mehr als 1 Überlebenden gibt
while (anzFalse < n) {
for (int counter = 0; counter < k; counter++) {
pos = pos + 1
//wenn die nächsten schon tot sind, werden sie übersprungen
while (!kreis [pos.mod(n)]) {
pos = pos + 1
}
//den Gefangenen an dieser Position trifft es
if (counter == k - 1) {
kreis[pos.mod(n)] = false
anzFalse = anzFalse + 1
//das ist der Letzte
if (anzFalse == n) {
println ((pos.mod(n) + 1) + " überlebt")
} else {
println ((pos.mod(n) + 1) + " ist tot")
}
}
}
}
Der Kreis wird durch einen Array of boolean dargestellt. Wenn die Person an der jeweiligen Position im Array lebt, dann ist der Wert true, ansonsten false. Nun wird in einer Schleife abgezählt. Immer nach k Schritten trifft es einen Gefangenen. Ab der zweiten Runde werden diejenigen übersprungen, die bereits tot sind. Die Variable pos läuft immer weiter, mit pos.mod(n) wird wieder vorne begonnen, wenn die letzte Position erreicht worden ist.
Download des Artikels als PDF File