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.

Die Collatz-Folge (auch Hailstone-Folge genannt) ist ein bekanntes Zahlenproblem: Du startest mit einer Zahl und wendest immer wieder einfache Regeln an.

Das Spannende daran: Für jede getestete Startzahl landet man irgendwann bei 1 und bleibt dann in der Schleife 4, 2, 1 hängen. Ob das wirklich für alle positiven Zahlen gilt, ist historisch berühmt, weil es bis heute nicht allgemein bewiesen ist.

Für uns als Java-Einsteiger ist das Problem trotzdem ideal: Du trainierst Schleifen, Abbruchbedingungen, saubere Methodennamen und bekommst ein Gefühl dafür, wie man Zwischenschritte ausgibt.

Und ganz nebenbei lernst du, warum eine gute Abbruchbedingung oft wichtiger ist als die eigentliche Rechnung.

 

Problemstellung

Gegeben ist eine positive ganze Zahl n. Erzeuge die Collatz-Folge, indem du die folgenden Regeln wiederholst, bis du bei 1 ankommst.

  • Wenn n gerade ist: n = n / 2
  • Wenn n ungerade ist: n = 3 * n + 1
  • Abbruch: Stoppe, sobald n == 1 ist.
  • Constraint: Startwert ist eine positive Zahl (n > 0).

Mini-Beispiel (Startwert 6):

  1. 6 ist gerade -> 6 / 2 = 3
  2. 3 ist ungerade -> 3 * 3 + 1 = 10
  3. 10 ist gerade -> 10 / 2 = 5
  4. 5 ist ungerade -> 3 * 5 + 1 = 16
  5. ... weiter, bis 1 erreicht ist

 

Die Idee dahinter

Das Kernkonzept hier ist: Iteration mit klarer Abbruchbedingung. Du wiederholst eine Aktion so lange, bis ein Zustand erreicht ist, bei dem du sicher aufhören kannst.

Bei der Collatz-Folge ist dieser Zustand n == 1. Sobald du das sauber in eine Schleife gibst, ist der Rest nur noch eine kleine Verzweigung: gerade oder ungerade.

  • Start: n
  • Wiederhole: Regel anwenden
  • Stoppe: bei 1
  • Optional: Zwischenschritte ausgeben oder speichern

 

Schritt für Schritt zur Lösung

  1. Prüfe den Startwert: Wenn n <= 0, ist das eine ungültige Eingabe.
  2. Gib den Startwert aus oder füge ihn einer Liste hinzu (damit du die Folge siehst).
  3. Solange n != 1 gilt: wende genau eine Regel an.
  4. Wenn n gerade ist, halbiere es; sonst berechne 3 * n + 1.
  5. Gib den neuen Wert aus (oder speichere ihn) und gehe zur nächsten Runde.
  6. Wenn n am Ende 1 ist, brich sauber ab.

 

Java-Implementierung (Variante A: straightforward)

public class CollatzStraightforward {
    public static void main(String[] args) {
        printCollatzSequence(6);
        System.out.println();
        printCollatzSequence(7);
    }

    static void printCollatzSequence(long start) {
        if (start <= 0) {
            throw new IllegalArgumentException("start must be positive");
        }

        long n = start;
        System.out.println("Start: " + n);

        while (n != 1) {
            if (isEven(n)) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
            System.out.println(n);
        }
    }

    static boolean isEven(long n) {
        return n % 2 == 0;
    }
}

Diese Variante ist bewusst direkt: eine while-Schleife, eine Abbruchbedingung (n != 1) und ein if für gerade/ungerade.

Wichtig ist hier die Eingabeprüfung am Anfang. Ohne sie könntest du für 0 oder negative Werte in merkwürdige Zustände laufen.

Die Hilfsmethode isEven macht die Bedingung lesbarer und ist ein kleiner Schritt in Richtung sauberer Struktur.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

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

public class CollatzIdiomatic {

    public static void main(String[] args) {
        demo(6);
        demo(7);
        demo(1);
    }

    private static void demo(long start) {
        List<Long> seq = collatzSequence(start);
        System.out.println("Input: " + start);
        System.out.println("Length: " + seq.size());
        System.out.println("Sequence: " + joinAsText(seq));
        System.out.println();
    }

    static List<Long> collatzSequence(long start) {
        if (start <= 0) {
            throw new IllegalArgumentException("start must be positive");
        }

        List<Long> result = new ArrayList<>();
        long n = start;
        result.add(n);

        while (n != 1) {
            n = nextCollatz(n);
            result.add(n);
        }

        return result;
    }

    static long nextCollatz(long n) {
        if (n % 2 == 0) {
            return n / 2;
        }
        return 3 * n + 1;
    }

    static String joinAsText(List<Long> values) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.size(); i++) {
            if (i > 0) {
                sb.append(" -> ");
            }
            sb.append(values.get(i));
        }
        return sb.toString();
    }
}

Hier ist die Schleife immer noch iterativ, aber die Aufgaben sind klar getrennt: nextCollatz berechnet den nächsten Wert, collatzSequence baut die Folge auf.

Das ist oft die angenehmere Struktur, weil du die Logik leichter testen kannst: zum Beispiel nur nextCollatz für einzelne Werte.

Außerdem bekommst du eine echte Rückgabe (List<Long>), statt nur Ausgaben in der Konsole. Das ist praxisnah, weil du die Liste später weiterverarbeiten kannst.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1:

  • Eingabe: 6
  • Output (Folge): 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Beispiel 2:

  • Eingabe: 7
  • Output (Start der Folge): 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> ... -> 1

Beispiel 3:

  • Eingabe: 1
  • Output: 1 (die Schleife laeuft nicht, weil die Abbruchbedingung sofort erfuellt ist)

 

Typische Fehler

  • Falsche Abbruchbedingung: Zum Beispiel while (n > 1) ist zwar oft ok, aber du solltest bewusst wissen, warum du bei 1 stoppst. Mit n != 1 ist die Intention eindeutiger.
  • Startwert nicht validiert: Ohne Check für n <= 0 kann deine Methode unklar reagieren oder endlos laufen.
  • Off-by-one bei der Ausgabe: Manche geben den Startwert nicht aus oder geben 1 nicht mehr aus. Entscheide dich bewusst: Willst du Start und Ende in der Folge haben? (In den Beispielen: ja.)
  • Ungültige Datentypen: Mit int kann es schneller zu Überlauf kommen. Nutze für den Einstieg lieber long, besonders wenn du größere Startwerte testest.
  • Verwechslung gerade/ungerade: Ein kleiner Dreher wie n % 2 == 1 funktioniert für positive Zahlen, aber n % 2 != 0 ist robuster, falls du später doch mal andere Werte siehst.
  • Endlosschleife durch fehlendes Update: Wenn du in der Schleife vergisst, n neu zu setzen, bleibt die Bedingung unverändert und das Programm läuft ewig.
  • Zu viel Logik in einer Methode: Wenn Berechnung, Ausgabe und Formatierung vermischt sind, wird es schnell unübersichtlich. Variante B zeigt eine sauberere Trennung.

 

Fazit

Mit der Collatz-Folge hast du ein kompaktes Problem, an dem du Schleifen und vor allem Abbruchbedingungen sauber üben kannst.

Du hast gesehen, wie eine straightforward Lösung aussieht und wie man das Ganze idiomatischer strukturiert, indem man kleine Methoden und Rückgabewerte nutzt.