Tornen i Hanoi
I den här övningen ska du implementera pusslet Tornen i Hanoi med en rekursiv algoritm. Målet med spelet är att flytta alla skivor från en av de tre stängerna till en annan, enligt följande regler:
- Du kan bara flytta en skiva i taget.
- Du kan bara ta den översta skivan från en av staplarna och lägga den överst på en annan stapel.
- Du får inte lägga en större skiva ovanpå en mindre.
Algoritmen som visas är en implementation av spelet med fyra skivor och tre stänger kallade 'A', 'B' och 'C'. Koden innehåller två fel. Om du kör den kraschar konsolen eftersom den överskrider det maximala rekursionsdjupet. Kan du hitta felen och rätta till dem?
Den här övningen är en del av kursen
Datastrukturer och algoritmer i Python
Övningsinstruktioner
- Rätta till basfallet.
- Rätta till anropen till
hanoi()-funktionen.
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
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)