Algorytm Wieży Hanoi: Python, C++ Code
Sara Chen
Czym jest Wieża Hanoi?
Wieża Hanoi to matematyczna łamigłówka składająca się z trzech prętów i licznych krążków umieszczonych jeden nad drugim. Znana jest również jako Wieża Brahmy lub Wieża Lucasa, jak przedstawił ją francuski matematyk Edouard Lucas w 1883 roku. Ta łamigłówka opiera się na legendach o przesuwaniu złotych krążków pomiędzy trzema prętami.
Ta łamigłówka ma trzy pręty i zmienną liczbę ułożonych w stos dysków. Pręty te zaprojektowano jako wieże cykliczne. Zatem dyski o większej średnicy są ułożone na dole, a mniejsze na górze.
Na początek dostajemy trzy kołki lub pręty. Na jednym z nich (A, pokazanym w przykładzie) znajdują się wszystkie dyski ułożone w stos. Naszym celem jest przeniesienie całego stosu dysków z jednego pręta (A) na drugi (C), przestrzegając pewnych określonych zasad.
Oto wstępna konfiguracja układanki-
I to jest ostateczny cel-
Regulamin Wieży Hanoi
Oto kilka podstawowych zasad dotyczących Wieży Hanoi:
- Początkowy stan tej układanki, wszystkie dyski będą ułożone w jednym pręcie.
- Ostateczny stan jest taki, że wszystkie dyski z pręta pierwszego zostaną ułożone na pręcie drugim lub pręcie trzecim.
- W dowolnym momencie możemy przenieść dysk z jednego pręta na drugi.
- Z pręta możemy przesunąć jedynie najwyższy krążek.
- Dysku nie można umieścić na innym dysku, który jest mniejszy.
Oryginalna legenda dotyczyła przesunięcia 64 dysków. Kapłani mogli przesuwać jeden dysk na raz zgodnie z zasadami. Według legendy istniała przepowiednia, że jeśli uda im się ukończyć akt, nastąpi koniec świata. W sekcji złożoności czasowej pokażemy, że ustawienie Wieży Hanoi n dysków kosztowałoby 2^n – 1 ruch.
Zatem, gdyby kapłanom zajęło 1 sekundę przesunięcie dysków, całkowity czas potrzebny na rozwiązanie zagadki wyniósłby 2^64 – 1 sekundę lub 584,942,417,356 26 7 15 lat, XNUMX dni, XNUMX godzin i XNUMX sekund.
Algorytm dla Wieży Hanoi
Jednym z ogólnych sposobów rozwiązania Wieży Hanoi jest algorytm rekurencyjny. Najpierw musimy zdecydować się na dwa pręty lub kołki jako źródło i miejsce przeznaczenia, a zapasowy kołek będzie pomocniczy lub pomocniczy.
Oto kroki, aby rozwiązać zagadkę Wieży Hanoi:
- Przesuń górne n-1 krążków z kołka źródłowego na kołek pomocniczy.
- Następnie przenieś n-ty krążek z kołka źródłowego na kołek docelowy.
- Na koniec przesuń pozostałe dyski n-1 z kołka pomocniczego na kołek docelowy.
Note: Jeśli mamy pojedynczy dysk, możemy go bezpośrednio przenieść ze źródła do miejsca docelowego.
Jak rozwiązać zagadkę Wieża Hanoi
Zilustrujmy algorytm dla trzech dysków i rozważmy kołek A jako źródło, kołek B jako element pomocniczy i kołek C jako miejsce docelowe
Krok 1) Początkowo wszystkie krążki zostaną ułożone na kołku A.
Na tym etapie:
Źródło = Peg A
Miejsce docelowe = Peg C
Pomocnik = kołek B
Teraz musimy przenieść górne dyski n-1 ze źródła do pomocniczego.
Uwaga: Chociaż możemy przenosić tylko jeden dysk na raz, zmienia to nasz problem z problemu z 3 dyskami na problem z 2 dyskami, co jest wywołaniem rekurencyjnym.
Krok 2) Ponieważ wywołujemy rekursywne wywołanie z peg A, a celem jest peg B, użyjemy peg C jako pomocnika.
Zauważ, że ponownie znajdujemy się w pierwszym etapie tego samego problemu z wieżą Hanoi dla dwóch dysków.
Teraz musimy przenieść n-1 lub jeden krążek ze źródła do pomocniczego, przesuwając najmniejszy krążek z kołka A na kołek C.
Na tym etapie:
Źródło = kołek A
Miejsce docelowe = kołek B
Pomocnik = kołek C
Krok 3) Następnie, zgodnie z naszym algorytmem, n-ty lub drugi dysk należy przenieść do miejsca docelowego lub kołka B.
Na tym etapie:
Źródło = kołek A
Miejsce docelowe = kołek B
Pomocnik = kołek C
Krok 4) Teraz przeniesiemy dyski n-1 lub dysk jeden z elementu pomocniczego lub kołka C do miejsca docelowego lub kołka B zgodnie z trzecim etapem naszego algorytmu.
Na tym etapie:
Źródło = kołek A
Miejsce docelowe = kołek B
Pomocnik = kołek C
Krok 5) Po zakończeniu wywołania rekurencyjnego powrócimy do naszych poprzednich ustawień przy pierwszym etapie algorytmu.
Krok 6) Teraz w drugim etapie przeniesiemy nasze źródło do miejsca docelowego, czyli przeniesienia krążka 3 na kołek C z kołka A.
Na tym etapie:
Źródło = kołek A
Miejsce docelowe = kołek C
Pomocnik = kołek B
Krok 7) Teraz możemy to zobaczyć
d polega na przeniesieniu pozostałych krążków z pola pomocniczego (kołek B) do miejsca docelowego (kołek C). W tym przypadku użyjemy początkowego źródła lub kołka A jako pomocy.
Krok 8) Ponieważ nie możemy przenieść dwóch dysków jednocześnie, wywołamy wywołanie rekurencyjne dla dysku 1. Zgodnie z ostatnim krokiem i naszym algorytm, miejscem docelowym na tym etapie jest kołek A.
Na tym etapie:
Źródło = kołek B
Miejsce docelowe = kołek A
Pomocnik = kołek C
Krok 9) Nasze wywołanie rekurencyjne zostało już zakończone. Następnie przenosimy dysk 2 od źródła do miejsca docelowego.
Na tym etapie:
Źródło = kołek B
Miejsce docelowe = kołek C
Pomocnik = kołek A
Krok 10) Następnie przenosimy pozostałe n-1 lub dysk 1 z pomocnika do miejsca docelowego.
Na tym etapie:
Źródło = kołek A
Miejsce docelowe = kołek C
Pomocnik = kołek B
Pseudokod Wieży Hanoi
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1, THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi (disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi (disk - 1, helper, dest, source)
END IF
END Procedure
Kod programu w C++
#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
if (num == 1) {
cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
return;
}
tower_of_hanoi(num - 1, source, helper, dest);
cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
int num;
cin >> num;
printf("The sequence of moves :\n");
tower_of_hanoi(num, "I", "III", "II");
return 0;
}
Wydajność
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
Kod programu w Python
def tower_of_hanoi(n, source, destination, helper):
if n==1:
print ("Move disk 1 from peg", source," to peg", destination)
return
tower_of_hanoi(n-1, source, helper, destination)
print ("Move disk",n," from peg", source," to peg", destination)
tower_of_hanoi(n-1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')
Wyjście:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
Złożoność Wieży Hanoi
Oto złożoność czasowa i przestrzenna Wieży Hanoi:
1) Złożoność czasowa:
Jeśli spojrzymy wstecz na nasz algorytm, zobaczymy, że dwukrotnie wprowadzamy rekurencyjne wywołanie dysków (n-1). Te rekurencyjne wywołania (n-1) dysków można podzielić na inne ((n-1)-1) i tak dalej, aż do przeniesienia tylko jednego dysku.
Na trzy dyski-
- Dysk 3 dwukrotnie wywołuje funkcję rekurencyjną dla dysku drugiego.
- Dysk 2 dwukrotnie wywołuje funkcję rekurencyjną dla dysku pierwszego.
- Dysk 1 może poruszać się w stałym czasie i czasie do rozwiązania dla trzech dysków.
= 2*(Czas rozwiązania dla dwóch dysków) + stała Czas przeniesienia dysku 3
= 2*(2*czas rozwiązania dla jednego krążka + stała Czas na przesunięcie krążka 2) + stała Czas na przesunięcie krążka 3
= (2*2) (stały czas na przesunięcie dysku 1) + 2*stały czas na przesunięcie dysku 2 + stały czas na przesunięcie dysku 3
Dla n dysków można to zapisać jako –
(2n-1 * stały czas przeniesienia dysku 1 + 2n-2 * stały czas przeniesienia dysku 2 + ….
Ten postęp geometryczny spowoduje O(2n-1) lub O (2n), co jest wykładnicze.
2) Złożoność kosmiczna
Złożoność przestrzenna Wieży Hanoi wynosi 0(n). Dzieje się tak, ponieważ musimy przechowywać sekwencję płyt. Gdy używamy rekurencji, używamy stosu. A maksymalny rozmiar stosu może wynosić „n”. Dlatego złożoność przestrzenna staje się O(n).
