Clojure - Torres de Hanoi (CPS) V94971
Sigui la funció (move n from to aux) que retorna la seqüència dels moviments que cal fer per resoldre el problema de les Torres de Hanoi per a n anelles o discos:
(defn move [n from to aux]
(if (= n 1)
[{:from from :to to}]
(concat
(move (dec n) from aux to)
[{:from from :to to}]
(move (dec n) aux to from))))
Si definim:
(defn torres-de-hanoi [n]
(move n "A" "C" "B"))
i executem (torres−de−hanoi 3) obtenim la seqüència (pretty printed):
({:from "A", :to "C"}
{:from "A", :to "B"}
{:from "C", :to "B"}
{:from "A", :to "C"}
{:from "B", :to "A"}
{:from "B", :to "C"}
{:from "A", :to "C"})
Es demana que transformeu aquesta funció a recursiva final fent servir CPS, anomenem-la move-cps, i després feu servir move-cps com a funció auxiliar per poder fer servir trampoline i definir la funció "trampolinitzada" move−t (l’execució de la qual consumeix una quantitat constant de pila d’execució).
Public test cases
Input
(towers-of-hanoi-t 3)
Output
({:from A, :to C} {:from A, :to B} {:from C, :to B} {:from A, :to C} {:from B, :to A} {:from B, :to C} {:from A, :to C})
Information
- Author
- Jordi Delgado / Gerard Escudero
- Language
- Catalan
- Official solutions
- Clojure
- User solutions
- Clojure