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 Pascalsche Dreieck ist ein bekanntes Zahlenmuster, das in Mathe, Informatik und sogar in Wahrscheinlichkeiten immer wieder auftaucht. Es wirkt auf den ersten Blick wie Magie, ist aber eigentlich ein sehr klares Konstrukt.
In der Programmierung ist es ein gutes Übungsproblem, weil du dabei verschachtelte Schleifen, Arrays und sauberes Indizieren trainierst. Genau diese Basics brauchst du später bei Tabellen, Gittern, dynamischen Programmen oder Auswertungen.
In diesem Artikel baust du das Dreieck Schritt für Schritt. Du bekommst zwei komplette Java-Lösungen: einmal straightforward und einmal als Alternative, die ohne 2D-Array auskommt.
Problemstellung
Erzeuge die ersten n Zeilen des Pascalschen Dreiecks und gib sie formatiert aus.
- Zeile 0 ist
1 - Jede Zeile beginnt und endet mit
1 - Jede innere Zahl ist die Summe der zwei Zahlen schräg darüber:
obenLinks + obenRechts - Eingabe: Anzahl der Zeilen
n(z.B.5) - Ausgabe: Die Zeilen des Dreiecks (z.B.
1,1 1,1 2 1, ...)
Mini-Beispiel (erste 5 Zeilen):
11 11 2 11 3 3 11 4 6 4 1
Die Idee dahinter
Du baust Zeile für Zeile. An den Rändern steht immer 1. Dazwischen gilt: wert = vorherigeZeile[j - 1] + vorherigeZeile[j].
Wenn du ein 2D-Array benutzt, ist die Vorstellung sehr greifbar: triangle[i][j] ist die Zahl in Zeile i an Position j.
- Zeile 0:
1 - Zeile 1:
1 1 - Zeile 2:
1 (1+1) 1 - Zeile 3:
1 (1+2) (2+1) 1
Schritt für Schritt zur Lösung
- Lege die Anzahl Zeilen fest. Das ist dein Parameter
rows. - Erzeuge eine Datenstruktur. Variante A nimmt ein 2D-Array, Variante B nur ein 1D-Array.
- Setze die Ränder. Für jede Zeile gilt: erste und letzte Position sind
1. - Berechne die inneren Werte. Nutze die Summe der zwei Werte aus der vorherigen Zeile.
- Gib das Ergebnis aus. Eine kleine Hilfsmethode sorgt für saubere Ausgabe.
Java-Implementierung (Variante A: straightforward)
public class PascalschesDreieckA {
public static void main(String[] args) {
int rows = 6;
int[][] triangle = buildTriangle(rows);
printTriangle(triangle);
}
static int[][] buildTriangle(int rows) {
if (rows < 0) {
throw new IllegalArgumentException("rows must be >= 0");
}
int[][] triangle = new int[rows][];
for (int i = 0; i < rows; i++) {
triangle[i] = new int[i + 1];
triangle[i][0] = 1;
triangle[i][i] = 1;
for (int j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
return triangle;
}
static void printTriangle(int[][] triangle) {
for (int i = 0; i < triangle.length; i++) {
System.out.println(joinRow(triangle[i]));
}
}
static String joinRow(int[] row) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < row.length; i++) {
if (i > 0) {
sb.append(' ');
}
sb.append(row[i]);
}
return sb.toString();
}
}Diese Variante ist sehr direkt: du speicherst wirklich das ganze Dreieck im int[][]. Die verschachtelten Schleifen sind klar: außen die Zeile, innen die Position in der Zeile. Praktisch ist auch das ragged array-Prinzip: jede Zeile hat genau die Länge, die sie braucht (i + 1).
Java-Implementierung (Variante B: Alternative oder Verbesserung)
public class PascalschesDreieckB {
public static void main(String[] args) {
int rows = 6;
printTriangle(rows);
}
static void printTriangle(int rows) {
if (rows < 0) {
throw new IllegalArgumentException("rows must be >= 0");
}
int[] current = new int[0];
for (int i = 0; i < rows; i++) {
current = nextRow(current);
System.out.println(joinRow(current));
}
}
static int[] nextRow(int[] prev) {
int[] row = new int[prev.length + 1];
row[0] = 1;
row[row.length - 1] = 1;
for (int j = 1; j < row.length - 1; j++) {
row[j] = prev[j - 1] + prev[j];
}
return row;
}
static String joinRow(int[] row) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < row.length; i++) {
if (i > 0) {
sb.append(' ');
}
sb.append(row[i]);
}
return sb.toString();
}
}Hier speicherst du nicht das komplette Dreieck, sondern nur prev und daraus die nächste Zeile. Das ist oft die idiomatischere Variante, wenn du nur die Ausgabe brauchst. Der Speicherverbrauch bleibt klein, und die Logik sitzt sauber in nextRow. Das Grundprinzip ist identisch, nur die Datenstruktur ist schlanker.
Beispiel: Eingabe und Ausgabe
Beispiel 1: Eingabe rows = 1, Ausgabe:
1
Beispiel 2: Eingabe rows = 5, Ausgabe:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Beispiel 3: Eingabe rows = 0, Ausgabe:
(keine Zeilen)
Typische Fehler
- Off-by-one in der inneren Schleife: Wenn du bei
jbis<= iläufst, schreibst du über den Rand oder überschreibst die1am Ende. - Ränder vergessen: Ohne
triangle[i][0] = 1undtriangle[i][i] = 1entstehen falsche Zeilen oder Defaultwerte0. - Falsche Quelle für die Summe: Die Summe kommt aus der vorherigen Zeile:
i - 1. Wenn du ausiliest, verwendest du Werte, die gerade erst gesetzt wurden. - 2D-Array falsch initialisiert:
new int[rows][rows]funktioniert, ist aber unnötig groß und verleitet zu falschen Indizes. Besser: jede Zeile mitnew int[i + 1]. - Negativen Parameter nicht behandeln: Bei
rows < 0sollte es eine klare Fehlermeldung geben, statt stillschweigend Unsinn zu machen. - Ausgabe mit zu vielen Leerzeichen: Wenn du nach jedem Element blind ein Leerzeichen dranhängst, wirkt die Ausgabe unsauber. Ein einfacher Trenner-Check (
if (i > 0)) löst das.
Fazit
Beim Pascalschen Dreieck lernst du, wie verschachtelte Schleifen sauber zusammenspielen und wie du Indizes kontrolliert benutzt. Du hast gesehen, wie ein 2D-Array die Struktur sehr anschaulich speichert, und wie eine 1D-Alternative denselben Effekt mit weniger Speicher erreicht.
