In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Das Josephus-Problem ist ein bekanntes Denk- und Programmierproblem: Menschen stehen im Kreis, und in einem festen Rhythmus wird immer wieder jemand entfernt, bis nur noch eine Person übrig ist.

Warum ist das so berühmt? Weil es sehr schön zeigt, wie man mit Zyklen, Modulo und einer Simulation arbeitet, ohne sich in komplizierte Mathematik zu verlieren.

In diesem Artikel baust du zuerst eine einfache Simulation (Variante A). Danach kommt eine bessere, idiomatischere Lösung (Variante B), die deutlich effizienter ist.

Am Ende kennst du typische Fehler, kannst Beispiele sicher nachvollziehen und hast zwei lauffähige Java-Programme als Vorlage.

 

Problemstellung

Es gibt n Personen, nummeriert von 1 bis n, die in einem Kreis stehen. Wir starten bei Person 1 und zählen immer k Personen weiter. Die Person, bei der wir landen, scheidet aus. Danach wird vom nächsten Platz aus weitergezählt. Das wiederholen wir, bis nur noch eine Person übrig ist.

  • Eingabe: n (Anzahl Personen), k (Schrittweite)
  • Ausgabe: die Nummer der letzten verbleibenden Person
  • Constraints (typisch): n >= 1, k >= 1

Mini-Beispiel mit n = 5, k = 2:

  1. Start: [1, 2, 3, 4, 5], wir zählen 2 weiter und entfernen 2
  2. Weiter ab 3: entfernen 4
  3. Weiter ab 5: entfernen 1
  4. Weiter ab 3: entfernen 5
  5. Übrig bleibt 3

 

Die Idee dahinter

Du bewegst dich in einem Zyklus (Kreis). Sobald du am Ende ankommst, springst du wieder nach vorne. Genau dafür ist Modulo praktisch.

Wenn du eine Liste mit aktueller Größe m hast und dich um s Schritte weiterbewegst, kannst du den nächsten Index so berechnen:

index = (index + s) % m

Beim Josephus-Problem ist das s aber k - 1, weil du die Person selbst mitzählst. Du gehst also k-1 Schritte weiter und entfernst dann genau diese Person.

  • Kreis mit Personen: 1 2 3 4 5
  • Start bei Index 0 (Person 1)
  • Bei k=2: springe immer um 1 weiter (also k-1)

 

Schritt für Schritt zur Lösung

  1. Validiere Eingaben: n und k müssen mindestens 1 sein.
  2. Lege eine Datenstruktur an: für die Simulation z.B. eine Liste mit 1..n.
  3. Merke dir einen aktuellen Index: starte bei 0 (erste Person).
  4. Berechne den nächsten Treffer: index = (index + (k - 1)) % size.
  5. Entferne die Person am Index: danach ist die Liste um 1 kleiner.
  6. Wiederhole bis nur noch 1 Person übrig ist: dann ist das Ergebnis die letzte Nummer.

 

Java-Implementierung (Variante A: straightforward)

import java.util.ArrayList; 
import java.util.List;

public class JosephusStraightforward {

  public static void main(String[] args) {
    System.out.println("n=5, k=2 -> " + solveBySimulation(5, 2));
    System.out.println("n=7, k=3 -> " + solveBySimulation(7, 3));
    System.out.println("n=1, k=5 -> " + solveBySimulation(1, 5));
  }

  public static int solveBySimulation(int n, int k) {
    validate(n, k);

    List<Integer> people = createPeople(n);
    int index = 0;

    while (people.size() > 1) {
      index = nextIndex(index, k, people.size());
      people.remove(index);
    }

    return people.get(0);
  }

  private static List<Integer> createPeople(int n) {
    List<Integer> people = new ArrayList<>(n);

    for (int i = 1; i <= n; i++) {
      people.add(i);
    }

    return people;
  }

  private static int nextIndex(int currentIndex, int k, int size) {
    int step = k - 1;

    return (currentIndex + step) % size;
  }

  private static void validate(int n, int k) {
    if (n < 1) {
      throw new IllegalArgumentException("n must be >= 1");
    }

    if (k < 1) {
      throw new IllegalArgumentException("k must be >= 1");
    }
  }
}

Diese Variante ist leicht zu verstehen: Du simulierst den Kreis, berechnest per Modulo den nächsten Index und entfernst die Person. Das passt super zum Lernen von Zyklen und Indexrechnung. Der Nachteil: Das Entfernen aus einer ArrayList kann bei größeren n schnell teuer werden, weil viele Elemente verschoben werden.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class JosephusIterative {

  public static void main(String[] args) {
    System.out.println("n=5, k=2 -> " + solveIterative(5, 2));
    System.out.println("n=7, k=3 -> " + solveIterative(7, 3));
    System.out.println("n=10, k=1 -> " + solveIterative(10, 1));
  }

  public static int solveIterative(int n, int k) {
    validate(n, k);

    int winnerIndex = 0; // 0-based winner for n=1

    for (int size = 2; size <= n; size++) {
      winnerIndex = (winnerIndex + k) % size;
    }

    return winnerIndex + 1; // back to 1-based person number
  }

  private static void validate(int n, int k) {
    if (n < 1) {
      throw new IllegalArgumentException("n must be >= 1");
    }

    if (k < 1) {
      throw new IllegalArgumentException("k must be >= 1");
    }
  }
}

Hier simulierst du nicht mehr alle Entfernungen, sondern baust das Ergebnis schrittweise auf: von 1 Person bis n Personen. Der Kern ist wieder Modulo, nur ohne Liste. Das läuft in der Praxis deutlich besser, weil du nur eine Schleife bis n hast und keine teuren Remove-Operationen.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1: n=5, k=2 ergibt 3.

Beispiel 2: n=7, k=3 ergibt 4.

Beispiel 3: n=10, k=1 ergibt 10 (weil immer der aktuelle entfernt wird und der letzte Platz übrig bleibt).

 

Typische Fehler

  • Off-by-one beim Schritt: In der Simulation ist es k - 1 Schritte bis zur zu entfernenden Person, nicht k.
  • Index nach dem Entfernen falsch behandelt: Nach remove(index) zeigt derselbe Index bereits auf die nächste Person. Du darfst dann nicht automatisch index++ machen.
  • Modulo mit alter Größe: Der Modulo muss immer mit der aktuellen Größe gerechnet werden (people.size() nach jeder Entfernung beachten).
  • 0-based vs 1-based verwechselt: Variante B rechnet intern 0-based und gibt am Ende winnerIndex + 1 zurück.
  • Falsche Abbruchbedingung: In der Simulation muss die Schleife laufen, solange size > 1 gilt, nicht bis size == 0.
  • k nicht validiert: Bei k=0 würdest du in Variante B falsche Ergebnisse bekommen oder Logikfehler produzieren.
  • Zu große Datenstruktur ohne Grund: Für reine Gewinnerberechnung ist eine Liste nicht nötig; das kostet Speicher und Zeit.

 

Fazit

Das Josephus-Problem ist perfekt, um Zyklen, Modulo und eine saubere Iteration zu üben. Variante A zeigt dir eine greifbare Simulation mit Liste und Index, ideal zum Verstehen. Variante B zeigt dir, wie man dasselbe Ergebnis mit einer kleinen, schnellen Schleife erreicht.