Optimierte Berechnung
Ganze Reihen berechnen
Wir können die Berechung optimieren, indem wir nicht jede Wegezahl aus zwei vorhergehenden Wegen berechnen, sondern ganze Reihen berechnen. Der Berechnung liegt folgende Idee zu Grunde:
Reihe 4: 1 3 3 1
Rechnung: 0 1 3 3 1
+ 1 3 3 1 0
Reihe 5: 1 4 6 4 1
Bei der Implementierung ist die Funktion map2 hilfreich,
die z.B. so benutzt werden kann:
> List.map2 (\name punkte -> name ++ ":" ++ String.fromInt punkte) ["Anna", "Bob"][80, 70]
["Anna:80","Bob:70"] : List String
Aufgabe 1
(a) Beschreibe was die Funktion List.map2 macht.
Gib die Signatur der Funktion (durch Überlegung) an und überprüfe
deine Vermutung in der REPL oder mit Hilfe der Elm-Dokumentation.
Implementiere eine Funktion nextRow, die aus einer Reihe,
gegeben durch eine Liste von Zahlen, eine neue Reihe berechnet und so
aufgerufen werden kann:
> nextRow [1, 3, 3, 1]
[1,4,6,4,1] : List Int
Rekursive Problemlösung
Um das Problem auf diese Art rekursiv zu lösen, müssen wir wieder zwei Fragen klären:
- Wann ist das Problem so einfach, dass wir direkt eine Lösung angeben können? Was ist also unser Basisfall? (Oder falls es mehrere gibt: Was sind unsere Basisfälle? Tipp: Hier gibt es nur einen.)
- Wie können wir unsere Problem auf gleichartige, aber kleinere Probleme reduzieren? Hier bedeutet das: Wie können wir die n-te Reihe aus der n-1-ten Reihe berechnen?
Aufgabe 2
(a) Beschreibe den Basisfall und wie das Problem reduziert werden kann.
(b) Implementiere die rekursive Funktion galtonRow,
die so aufgerufen werden kann:
> galtonRow 5
[1,4,6,4,1] : List Int
(c) Teste die Funktion für größere Zahlen. Beschreibe das auftretende Problem, das noch vor der maximalen Rekursionstiefe auftritt.
(d) Optional: Du hast gesehen, dass die maximale Rekursionstiefe hier nicht das relevante Problem ist. Zur Übung kannst du die Funktion aber dennoch endrekursiv implementieren.