Maximale Summe in einem Zahlendreieck

1. Aufgabe

Gegenstand dieser Aufgabe sind Zahlendreiecke, zum Beispiel wie in Abbildung 1 gezeigt:

Zahlendreieck mit vier Zeilen.

Abbildung 1. Zahlendreieck mit vier Zeilen.


Gesucht ist ein Pfad mit Zahlen im Dreieck, deren Summe den größtmöglichen Wert annimmt. Dabei wird vorausgesetzt, dass jeder Pfad stets mit der obersten Zahl des Dreiecks beginnt und dann immer aus den zwei unteren, nächstliegenden Zahlen solange gebildet wird, bis man dann ganz unten angekommen ist. Im vorliegenden Beispiel würde der Pfad 1 ⇒ 5 ⇒ 5 ⇒ 3 lauten und die maximale Summe 14 ergeben. Mit keinem anderen Pfad durch das Zahlendreieck erhält man einen Summenwert größer als 14!

Um die maximale Summe zu berechnen, können Sie mit einem Brute-Force-Ansatz an das Problem herangehen. In diesem Fall würden Sie schlicht und ergreifend alle zulässigen Pfade des Dreiecks aufsummieren, um auf diese Weise den größten Summenpfadwert zu erhalten. Zum Zwecke des reinen Übens wäre dieser Ansatz gar nicht so verwerflich, nur führt er bei großen Dreiecken nicht in einer akzeptablen Programmlaufzeit zum Ziel.

Mit etwas Nachdenken können wir einen zweiten Lösungsansatz ins Spiel bringen, der die Lösung an Hand einer Rekursion aufspürt. Wenn wir die oberste Zahl des Dreiecks betrachten, stehen wir vor der Frage, ob wir mit der linken oder rechten unteren Zahl den maximalen Summenpfad einschlagen. Die richtige Entscheidung könnten wir treffen, wenn wir wüssten, welche Summe wir jeweils erzielen. Um die optimale Wahl (die mit dem größtmöglichen Summenpfad) treffen zu können, müssten wir wissen, wie groß die Summen sind, die wir bekommen, wenn wir in beide Richtungen gehen. Diese Frage können wir aber dadurch beantworten, indem wir das Ausgangsproblem auf zwei kleinere Probleme (zweier kleinerer Dreiecke) zurückgeführt haben. In Abbildung 2 finden Sie die beiden kleineren Zahlendreiecke grafisch hervorgehoben vor:

Reduzierung des Zahlendreieck-Problems auf zwei kleinere Zahlendreieck-Probleme.

Abbildung 2. Reduzierung des Zahlendreieck-Problems auf zwei kleinere Zahlendreieck-Probleme.


Wir können jedes der Teilprobleme in einer ähnlichen Art und Weise solange herunterbrechen, bis wir bei einem Teildreieck angekommen sind, dass nur noch aus einer einzigen Zahl besteht. In diesem Fall ist die Frage des maximalen Summenpfads trivial zu beantworten, es ist die Zahl selbst. Nun können wir wieder eine Zeile nach oben gehen, für die zu beantwortenden Frage gibt es genau eine Lösung, sie lautet A + Max(B,C), siehe dazu auch Abbildung 3:

Lösung des kleinsten Zahlendreieck-Problems: A + Max(B,C).

Abbildung 3. Lösung des kleinsten Zahlendreieck-Problems: A + Max(B,C).


Um beim Beispiel aus Abbildung 3 zu bleiben: Sobald wir die Antwort auf alle drei Unterprobleme aus der vorletzten Zeile kennen, können wir wiederum eine Zeile nach oben gehen und die gestellte Frage von zwei Unterproblemen beantworten. Es kommt dabei wieder die gleiche Formel zur Anwendung. Diesen Vorgang wiederholen wir solange, bis wir beim obersten Element des Dreiecks angekommen sind.

Wenn wir den rekursiven Ansatz sinnvoll umsetzen, sollten wir die Summe zu einem bestimmten Teildreieck nicht mehrfach berechnen. Mit einer geeigneten Optimierung lassen sich auf diese Weise für den rekursiven Ansatz – im Gegensatz zum Brute-Force-Vorgehen – gute Laufzeiten erzielen.

Der rekursive Lösungsweg ermöglicht es, die maximale Summe des Zahlendreiecks zu ermitteln. Es gelingt dabei aber nicht, den Pfad selbst festzuhalten. Um diesen auch noch zu bestimmen, muss man zunächst zu einer erweiterten Datenstruktur übergehen. Neben dem Dreieck mit den Zahlen legen wir ein zweites Dreieck derselben Größenordnung an. In diesem legen wir pro Element einen Summenwert und eine Kennung ab, die aussagt, ob wir in der nächsten Zeile den Pfad nach links oder rechts einzuschlagen haben. Die Konstruktion dieses Dreiecks beginnen wir in der letzten Zeile und arbeiten uns Zeile für Zeile nach oben durch. Am besten betrachten wir dazu das Beispiel aus Abbildung 1, das korrespondierende Hilfsdreieck finden Sie in Abbildung 4 vor:

Konstruktionsunterstützung: Teilsummenbildung und Wegekennung.

Abbildung 4. Konstruktionsunterstützung: Teilsummenbildung und Wegekennung.


In der untersten Zeile aus Abbildung 4 gibt es weder Summen – die Zahlen stehen für sich – noch eine Wegekennung. In der zweiten Zeile von unten betrachtet ist 4 + 5 größer als 4 + 2, wir notieren deshalb die Summe 9 und die Wegekennung “L”, sprich nach “links verzweigend”, wenn wir den Pfad von der zweituntersten zur untersten Zeile begehen. 1 + 2 ist kleiner als 1 + 3, wir notieren die Summe 4 mit der Wegekennung “R”. Der dritte und letzte Eintrag der zweituntersten Zeile ergibt sich zu “8/L”, da 5 + 3 (Summe 8) größer als 5 + 1 ist. In der zweitobersten Zeile lautet der erste Eintrag “11/L”, da 2 + 9 größer als 2 + 4 ist. Entsprechend ergibt sich der zweite Eintrag zu “13/R”, da 5 + 4 kleiner als 5 + 8 ist. Damit sind wir schon an der Spitze des Dreiecks angekommen. In der zweitobersten Zeile steht der größere Eintrag rechts, deshalb lautet die letzte Eintragung “14/R”. Um den Pfad auszugeben, müssen wir mit der obersten Eintragung beginnen und entsprechend der Wegekennungen uns von Zeile von Zeile nach unten durchhangeln.

Im Gegensatz zum rekursiven Absatz ist dieser Lösungsstrategie iterativ und sie benötigt eine erweiterte Datenstruktur, in der die Teilsummen und die Wegekennungen abgespeichert werden. Im rekursiven Lösungsansatz fallen die Wegekennungen, also die Pfadbestimmung, weg. Die Teilsummen können als lokale Variablen auf dem Methodenaufrufstapel abgelegt werden, womit sie allerdings jedes Mal neu zu berechnen sind. Verbessert kann der rekursive Lösungsansatz durch eine zusätzliche Datenstruktur (Cache) werden, in dem einmal berechnete Teilsummen zwischengespeichert werden.

Erstellen Sie eine Klasse Triangle mit entsprechenden Methoden, um für beliebige Zahlendreiecke die maximale Summe und den dazugehörigen Pfad zu bestimmen. Implementieren Sie alle drei skizzierten Lösungsansätze (brute-force, rekursiv und iterativ) und vergleichen Sie die Laufzeiten.

2. Lösung

Um die drei Lösungsansätze voneinander unabhängig gestalten zu können, finden Sie im Folgenden drei Klassen BruteForceSolver, RecursiveSolver und ExtendedTriangleSolver mit ihrer jeweiligen, völlig eigenständigen Implementierung vor. Es gibt aber auch einige gemeinsame Tätigkeiten, wie etwa das Einlesen des Zahlendreiecks oder seine Ausgabe auf der Konsole. Diese Programmteile sind, ganz im Sinne der Objektorientierung, in einer Basisklasse Triangle angesiedelt (Listing 1):

01: abstract class Triangle
02: {
03:     protected int rows;
04:     protected int[][] triangle;
05: 
06:     public Triangle()
07:     {
08:         this.rows = 0;
09:         this.triangle = null;
10:     }
11: 
12:     // public interface
13:     public abstract int Sum { get; }
14:     public abstract void Solve();
15: 
16:     // properties
17:     public int Rows
18:     {
19:         set
20:         {
21:             this.rows = value;
22:             this.triangle = new int[value][];
23:         }
24: 
25:         get
26:         {
27:             return this.rows;
28:         }
29:     }
30: 
31:     // input helper method
32:     public void ConstructLine(int row, int[] numbers)
33:     {
34:         int[] line = new int[numbers.Length];
35: 
36:         for (int i = 0; i < numbers.Length; i++)
37:             line[i] = numbers[i];
38: 
39:         this.triangle[row] = line;
40:     }
41: 
42:     // overrides
43:     public override String ToString()
44:     {
45:         String s = "";
46:         for (int i = 0; i < this.rows; i++)
47:         {
48:             for (int j = 0; j < this.triangle[i].Length; j++)
49:                 s += String.Format("{0,5}", this.triangle[i][j].ToString());
50: 
51:             s += Environment.NewLine;
52:         }
53:         return s;
54:     }
55: }

Beispiel 1. Klasse Triangle: Basisklasse.


Die Klasse Triangle stellt eine abstrakte Basisklasse dar, ihre beiden abstrakten Elemente Sum (Eigenschaft) und Solve (Methode) stellen die Vorgabe für alle Spezialisierungen dar:

public abstract int Sum { get; }
public abstract void Solve();

Nun folgen gemäß Spezifikation die Implementierungen der drei Klassen BruteForceSolver, RecursiveSolver und ExtendedTriangleSolver:

01: class BruteForceSolver : Triangle
02: {
03:     private int sum;
04: 
05:     public BruteForceSolver()
06:     {
07:         this.sum = 0;
08:     }
09: 
10:     // public interface
11:     public override int Sum
12:     {
13:         get
14:         {
15:             return this.sum;
16:         }
17:     }
18: 
19:     public override void Solve()
20:     {
21:         this.SolverHelper(0, 0, 0);
22:     }
23: 
24:     private void SolverHelper(int sum, int row, int col)
25:     {
26:         sum += this.triangle[row][col];
27:         
28:         if (row == this.triangle.Length - 1)
29:         {
30:             if (sum > this.sum)
31:                 this.sum = sum;
32:         }
33:         else
34:         {
35:             this.SolverHelper(sum, row + 1, col);
36:             this.SolverHelper(sum, row + 1, col + 1);
37:         }
38:     }
39: }

Beispiel 2. Klasse BruteForceSolver.


01: class RecursiveSolver : Triangle
02: {
03:     private int sum;
04:     private int[][] cache;
05: 
06:     public RecursiveSolver()
07:     {
08:         this.sum = 0;
09:         this.cache = null;
10:     }
11: 
12:     // properties
13:     public override int Sum
14:     {
15:         get
16:         {
17:             return this.sum;
18:         }
19:     }
20: 
21:     // public interface
22:     public override void Solve()
23:     {
24:         this.InitCache();
25:         this.sum = this.SumOfSubTriangle(0, 0);
26:     }
27: 
28:     // private helper methods
29:     private int SumOfSubTriangle(int row, int col)
30:     {
31:         // value already computed
32:         if (this.cache[row][col] != -1)
33:             return this.cache[row][col];
34: 
35:         int sum = this.triangle[row][col];
36: 
37:         if (row == this.triangle.Length - 1)
38:         {
39:             sum = this.triangle[row][col];
40:         }
41:         else
42:         {
43:             int sum1 = this.cache[row + 1][col];
44:             int sum2 = this.cache[row + 1][col + 1];
45: 
46:             if (sum1 != -1 && sum2 != -1)
47:             {
48:                 sum += Math.Max(sum1, sum2);
49:             }
50:             else if (sum1 != -1)
51:             {
52:                 sum += Math.Max(sum1, SumOfSubTriangle(row + 1, col + 1));
53:             }
54:             else if (sum2 != -1)
55:             {
56:                 sum += Math.Max(SumOfSubTriangle(row + 1, col), sum2);
57:             }
58:             else
59:                 sum += Math.Max(
60:                     SumOfSubTriangle(row + 1, col),
61:                     SumOfSubTriangle(row + 1, col + 1));
62:         }
63: 
64:         // update cache
65:         this.cache[row][col] = sum;
66: 
67:         return sum;
68:     }
69: 
70:     public void InitCache()
71:     {
72:         this.cache = new int[this.rows][];
73: 
74:         for (int i = 0; i < this.rows; i++)
75:         {
76:             int[] line = new int[this.triangle[i].Length];
77:             for (int j = 0; j < line.Length; j++)
78:                 line[j] = -1;
79: 
80:             this.cache[i] = line;
81:         }
82:     }
83: }

Beispiel 3. Klasse RecursiveSolver.


Die Klasse ExtendedTriangleSolver bedient sich einer Hilfsklasse Entry. Sie ist gemäß Vorgabe von Abbildung 4 konzipiert, um für eine iterative Bottom-Up-Strategie die Zwischensummen und die jeweilige Wegekennung pro Zahl des Dreiecks aufzunehmen:

01: enum Direction { Left, Right };
02: 
03: class Entry
04: {
05:     public int sum;
06:     public Direction direction;
07: 
08:     // c'tor
09:     public Entry(int value)
10:     {
11:         this.sum = 0;
12:         this.direction = Direction.Left;
13:     }
14: 
15:     public override String ToString()
16:     {
17:         return String.Format("[{0}/{1}]",
18:             this.sum, this.direction);
19:     }
20: }

Beispiel 4. Klasse Entry: Hilfsklasse für Klasse ExtendedTriangleSolver.


001: class ExtendedTriangleSolver : Triangle
002: {
003:     private Entry[][] entries;
004: 
005:     public ExtendedTriangleSolver()
006:     {
007:         this.entries = null;
008:     }
009: 
010:     public override int Sum
011:     {
012:         get
013:         {
014:             return this.entries[0][0].sum;
015:         }
016:     }
017: 
018:     public String Path
019:     {
020:         get
021:         {
022:             String s = "";
023: 
024:             int column = 0;
025:             for (int i = 0; i < this.rows; i++)
026:             {
027:                 // int value = this.entries[i][column].value;
028:                 int value = this.triangle[i][column];
029:                 s += value.ToString();
030: 
031:                 if (this.entries[i][column].direction == Direction.Right)
032:                     column ++;
033: 
034:                 if (i < this.rows - 1)
035:                     s += " => ";
036:             }
037:             return s;
038:         }
039:     }
040: 
041:     // public interface
042:     public override void Solve()
043:     {
044:         this.ConstructExtendedTriangle();
045:         this.ComputeSumBottomUp();
046:     }
047: 
048:     // private helper methods
049:     public void ConstructExtendedTriangle()
050:     {
051:         this.entries = new Entry[this.rows][];
052: 
053:         for (int i = 0; i < this.rows; i++)
054:         {
055:             Entry[] line = new Entry[this.triangle[i].Length];
056: 
057:             for (int j = 0; j < this.triangle[i].Length; j++)
058:             {
059:                 Entry entry = new Entry(this.triangle[i][j]);
060:                 line[j] = entry;
061:             }
062: 
063:             this.entries[i] = line;
064:         }
065:     }
066: 
067:     public void ComputeSumBottomUp()
068:     {
069:         for (int i = this.rows - 1; i >= 0; i--)
070:         {
071:             if (i == this.rows - 1)
072:             {
073:                 for (int j = 0; j < this.entries[i].Length; j++)
074:                 {
075:                     this.entries[i][j].sum = this.triangle[i][j];
076:                     this.entries[i][j].direction = Direction.Left;  // irrelevant
077:                 }
078:             }
079:             else
080:             {
081:                 for (int j = 0; j < this.entries[i].Length; j++)
082:                 {
083:                     int sum1 = this.entries[i + 1][j].sum;
084:                     int sum2 = this.entries[i + 1][j + 1].sum;
085: 
086:                     if (sum1 >= sum2)
087:                     {
088:                         this.entries[i][j].sum = this.triangle[i][j] + sum1;
089:                         this.entries[i][j].direction = Direction.Left;
090:                     }
091:                     else
092:                     {
093:                         this.entries[i][j].sum = this.triangle[i][j] + sum2;
094:                         this.entries[i][j].direction = Direction.Right;
095:                     }
096:                 }
097:             }
098:         }
099:     }
100: 
101:     // overrides
102:     public override String ToString()
103:     {
104:         String s = "";
105: 
106:         if (this.entries != null)
107:         {
108:             for (int i = 0; i < this.rows; i++)
109:             {
110:                 for (int j = 0; j < this.entries[i].Length; j++)
111:                     s += String.Format("{0,3} {1,-14}",
112:                         this.triangle[i][j], this.entries[i][j]);
113: 
114:                 s += Environment.NewLine;
115:             }
116:         }
117: 
118:         return s;
119:     }
120: }

Beispiel 5. Klasse ExtendedTriangleSolver.


Zum Testen der Implementierungen benutzen wir ein etwas umfangreicheres Zahlendreieck:

class Program
{
    public static void Main()
    {
        Test02_BruteForce(); 
        Console.WriteLine();
        
        Test02_Recursive();
        Console.WriteLine();

        Test02_Extended();
    }

    private static void Test02_BruteForce ()
    {
        BruteForceSolver solver = new BruteForceSolver ();

        solver.Rows = 15;
        solver.ConstructLine(0,  new int[] { 75 });
        solver.ConstructLine(1,  new int[] { 95, 44 });
        solver.ConstructLine(2,  new int[] { 17, 47, 42 });
        solver.ConstructLine(3,  new int[] { 18, 35, 87, 10 });
        solver.ConstructLine(4,  new int[] { 20, 04, 82, 47, 65 });
        solver.ConstructLine(5,  new int[] { 19, 01, 23, 75, 03, 34 });
        solver.ConstructLine(6,  new int[] { 88, 02, 77, 73, 07, 63, 67 });
        solver.ConstructLine(7,  new int[] { 99, 65, 04, 28, 06, 16, 70, 92 });
        solver.ConstructLine(8,  new int[] { 41, 41, 26, 56, 83, 40, 80, 70, 33 });
        solver.ConstructLine(9,  new int[] { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 });
        solver.ConstructLine(10, new int[] { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 });
        solver.ConstructLine(11, new int[] { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 });
        solver.ConstructLine(12, new int[] { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 });
        solver.ConstructLine(13, new int[] { 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 });
        solver.ConstructLine(14, new int[] { 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23 });

        Console.Write(solver);
        solver.Solve();
        Console.WriteLine("Sum:  {0}", solver.Sum);
    }

    private static void Test02_Recursive()
    {
        RecursiveSolver solver = new RecursiveSolver();

        solver.Rows = 15;
        solver.ConstructLine(0,  new int[] { 75 });
        solver.ConstructLine(1,  new int[] { 95, 44 });
        solver.ConstructLine(2,  new int[] { 17, 47, 42 });
        solver.ConstructLine(3,  new int[] { 18, 35, 87, 10 });
        solver.ConstructLine(4,  new int[] { 20, 04, 82, 47, 65 });
        solver.ConstructLine(5,  new int[] { 19, 01, 23, 75, 03, 34 });
        solver.ConstructLine(6,  new int[] { 88, 02, 77, 73, 07, 63, 67 });
        solver.ConstructLine(7,  new int[] { 99, 65, 04, 28, 06, 16, 70, 92 });
        solver.ConstructLine(8,  new int[] { 41, 41, 26, 56, 83, 40, 80, 70, 33 });
        solver.ConstructLine(9,  new int[] { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 });
        solver.ConstructLine(10, new int[] { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 });
        solver.ConstructLine(11, new int[] { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 });
        solver.ConstructLine(12, new int[] { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 });
        solver.ConstructLine(13, new int[] { 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 });
        solver.ConstructLine(14, new int[] { 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23 });

        Console.Write(solver);
        solver.Solve();
        Console.WriteLine("Sum: {0}", solver.Sum);
    }

    private static void Test02_Extended()
    {
        ExtendedTriangleSolver solver = new ExtendedTriangleSolver();

        solver.Rows = 15;
        solver.ConstructLine(0,  new int[] { 75 });
        solver.ConstructLine(1,  new int[] { 95, 44 });
        solver.ConstructLine(2,  new int[] { 17, 47, 42 });
        solver.ConstructLine(3,  new int[] { 18, 35, 87, 10 });
        solver.ConstructLine(4,  new int[] { 20, 04, 82, 47, 65 });
        solver.ConstructLine(5,  new int[] { 19, 01, 23, 75, 03, 34 });
        solver.ConstructLine(6,  new int[] { 88, 02, 77, 73, 07, 63, 67 });
        solver.ConstructLine(7,  new int[] { 99, 65, 04, 28, 06, 16, 70, 92 });
        solver.ConstructLine(8,  new int[] { 41, 41, 26, 56, 83, 40, 80, 70, 33 });
        solver.ConstructLine(9,  new int[] { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 });
        solver.ConstructLine(10, new int[] { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 });
        solver.ConstructLine(11, new int[] { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 });
        solver.ConstructLine(12, new int[] { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 });
        solver.ConstructLine(13, new int[] { 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 });
        solver.ConstructLine(14, new int[] { 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23 });

        solver.Solve();
        Console.Write(solver); 
        Console.WriteLine("Sum:  {0}", solver.Sum);
        Console.WriteLine("Path: {0}", solver.Path);
    }
}

Ausgabe:

   75
   95   44
   17   47   42
   18   35   87   10
   20    4   82   47   65
   19    1   23   75    3   34
   88    2   77   73    7   63   67
   99   65    4   28    6   16   70   92
   41   41   26   56   83   40   80   70   33
   41   48   72   33   47   32   37   16   94   29
   53   71   44   65   25   43   91   52   97   51   14
   70   11   33   28   77   73   17   78   39   68   17   57
   91   71   52   38   17   14   91   43   58   50   27   29   48
   63   66    4   68   89   53   67   30   73   16   69   87   40   31
    4   62   98   27   23    9   70   98   73   93   38   53   60    4   23
Sum:  1070

   75
   95   44
   17   47   42
   18   35   87   10
   20    4   82   47   65
   19    1   23   75    3   34
   88    2   77   73    7   63   67
   99   65    4   28    6   16   70   92
   41   41   26   56   83   40   80   70   33
   41   48   72   33   47   32   37   16   94   29
   53   71   44   65   25   43   91   52   97   51   14
   70   11   33   28   77   73   17   78   39   68   17   57
   91   71   52   38   17   14   91   43   58   50   27   29   48
   63   66    4   68   89   53   67   30   73   16   69   87   40   31
    4   62   98   27   23    9   70   98   73   93   38   53   60    4   23
Sum: 1070

 75 [1070/Left]
 95 [995/Right]    44 [944/Left]
 17 [818/Right]    47 [900/Right]    42 [895/Left]
 18 [704/Left]     35 [801/Right]    87 [853/Left]     10 [792/Right]
 ...
 ...
 ...

  4 [4/Left]       62 [62/Left]      98 [98/Left]      27 [27/Left]      23 [23/Left] ...
Sum:  1070

Path: 75 => 95 => 47 => 87 => 82 => 75 => 73 => 28 => 83 => 32 => 91 => 78 => 58 => 73 => 93

Interessant an der Programmausführung ist die Ausgabe des Zahlendreiecks in der erweiterten Form. Man kann gut (in Ausschnitten) erkennen, wie das Ergebnis Zeile für Zeile bottom-up gebildet wird.