Wieże Hanoi
W tym ćwiczeniu zaimplementujesz łamigłówkę Wież Hanoi za pomocą algorytmu rekurencyjnego. Celem gry jest przeniesienie wszystkich dysków z jednego z trzech prętów na inny, zgodnie z następującymi zasadami:
- Jednocześnie można przenosić tylko jeden dysk.
- Można zdjąć wyłącznie górny dysk ze stosu i umieścić go na szczycie innego stosu.
- Nie można kłaść większego dysku na mniejszym.
Przedstawiony algorytm to implementacja tej gry z czterema dyskami i trzema prętami o nazwach „A", „B" i „C". Kod zawiera dwa błędy. Jeśli go uruchomisz, konsola zgłosi błąd – zostanie przekroczona maksymalna głębokość rekurencji. Czy uda ci się znaleźć usterki i je naprawić?
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Instrukcje do ćwiczenia
- Popraw przypadek bazowy.
- Popraw wywołania funkcji
hanoi().
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
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)