Implementierung in Elm
Rekursion in Elm
Du hast auf der vorherigen Seite eine rekursive Strategie für die Türme von Hanoi entwickelt, also eine Strategie, bei der eine Funktion sich selbst aufruft. Nun wollen wir diese Strategie in Elm implementieren. Hier siehst du ein einfaches Beispiel für eine rekursive Funktion in Elm:
hallo : Int -> String
hallo n =
if n == 0 then
""
else
"Hallo " ++ hallo (n - 1)
Aufgabe 1
Überlege dir, was die Funktion
hallo macht und wie sie funktioniert.
Teste die Funktion in der Elm-REPL.
Implementierung der Türme von Hanoi
Ziel ist nun eine Funktion zu schreiben, die die Schritte zum Lösen des Problems der Türme von Hanoi als Liste von einzelnen Schritten zurückgibt. Ein Aufruf in der REPL könnte dann so aussehen:
> bewegeTurm 3 "A" "B" "C"
["A -> C","A -> B","C -> B","A -> C","B -> A","B -> C","A -> C"]
Aufgabe 2
Ersetze die Fragezeichen in der Funktion
bewegeTurm durch die richtigen Ausdrücke.
Teste die Funktion in der REPL und überprüfe, ob sie korrekt funktioniert,
indem du die berechneten Schritte selbst durchführst.
bewegeTurm : Int -> String -> String -> String -> List String
bewegeTurm n x y z =
if ??? then
[ x ++ " -> " ++ z ]
else
bewegeTurm ??? x z y ++
[ x ++ " -> " ++ z ] ++
???
Aufgabe 3
Der Legende nach müssen die Mönche von Benares 64 goldene Scheiben
von einem Turm zu einem anderen bewegen.
Schätze ab, wie lange die Mönche brauchen bis sie fertig sind.
Gehe davon aus, dass die Mönche jede Sekunde eine Scheibe bewegen können.
Tipp: Du kannst die Anzahl der Schritte berechnen, indem du
die Länge der Liste für einen Turm von 1, 2, 3, ... Scheiben berechnen lässt.