Toren van Hanoi
In deze oefening implementeer je de puzzel Toren van Hanoi met een recursief algoritme. Het doel van dit spel is om alle schijven van één van de drie staven naar een andere te verplaatsen, volgens deze regels:
- Je mag maar één schijf tegelijk verplaatsen.
- Je mag alleen de bovenste schijf van een stapel nemen en boven op een andere stapel leggen.
- Je mag geen grotere schijf op een kleinere leggen.
Het getoonde algoritme is een implementatie van dit spel met vier schijven en drie staven met de namen ‘A’, ‘B’ en ‘C’. De code bevat twee fouten. Als je het uitvoert, crasht de console zelfs omdat de maximale recursiediepte wordt overschreden. Kun je de bugs vinden en oplossen?
Deze oefening maakt deel uit van de cursus
Datastructuren en algoritmen in Python
Oefeninstructies
- Corrigeer het basisgeval.
- Corrigeer de aanroepen van de functie
hanoi().
Praktische interactieve oefening
Probeer deze oefening eens door deze voorbeeldcode in te vullen.
def hanoi(num_disks, from_rod, to_rod, aux_rod):
# Correct the base case
if num_disks >= 0:
# Correct the calls to the hanoi function
hanoi(num_disks, from_rod, aux_rod, to_rod)
print("Moving disk", num_disks, "from rod", from_rod,"to rod",to_rod)
hanoi(num_disks, aux_rod, to_rod, from_rod)
num_disks = 4
source_rod = 'A'
auxiliar_rod = 'B'
target_rod = 'C'
hanoi(num_disks, source_rod, target_rod, auxiliar_rod)