Algorytm Wieży Hanoi: Python, C++ Code

⚡ Inteligentne podsumowanie

Algorytm Wieży Hanoi to klasyczna łamigłówka rekurencyjna, w której stos dysków przesuwa się między trzema kołkami, nigdy nie umieszczając większego dysku na mniejszym, co doskonale ilustruje zasadę dziel i zwyciężaj.

🗼 Przygotowanie układanki: Trzy kołki i n dysków ułożonych w kolejności malejącej na kołku źródłowym, czekających na przeniesienie na kołek docelowy za pomocą kołka pomocniczego.
📜 zasady: W danym momencie może poruszać się tylko jeden krążek. Ruchomy może być tylko górny krążek na danym kołku, a większy krążek nie może spoczywać na mniejszym krążku.
🔁 Pomysł rekurencyjny: Przenieś n-1 dysków na kołek pomocniczy, przenieś największy dysk na kołek docelowy, a następnie przenieś n-1 dysków z kołka pomocniczego na docelowy.
⏱️. Złożoność czasowa: Rozwiązanie n dysków wymaga 2^n – 1 ruchów, co daje wykładniczą złożoność czasową O(2^n), która rośnie bardzo szybko wraz ze wzrostem n.
???? Złożoność przestrzeni: Stos rekurencji może pomieścić do n klatek naraz, więc złożoność przestrzenna rozwiązania rekursywnego wynosi O(n).
🛠️. Aplikacje: Nauczanie rekurencji, schematów rotacji kopii zapasowych, przenoszenia danych w oparciu o stos, sekwencjonowania w robotyce oraz zrozumienia projektowania algorytmów typu „dziel i zwyciężaj”.

Czytaj więcej

Czym jest Wieża Hanoi?

Wieża Hanoi to łamigłówka matematyczna składająca się z trzech prętów i stosu dysków o coraz mniejszej średnicy, umieszczonych jeden na drugim. Znana jest również jako Wieża Brahmy lub wieża Lucasa, od czasu, gdy francuski matematyk Edouard Lucas przedstawił ją w 1883 roku. Łamigłówka oparta jest na legendach o przesuwaniu złotych dysków między trzema prętami.

Ta łamigłówka składa się z trzech prętów i zmiennej liczby ułożonych w stos dysków. Pręty są ułożone w cykliczne wieże, więc większe dyski są ułożone na dole, a mniejsze na górze.

Na początek otrzymujemy trzy kołki lub pręty. Na jednym z nich (w przykładzie kołek A) znajdują się wszystkie dyski ułożone w stos. Celem jest przeniesienie całego stosu z jednego pręta (A) na drugi (C), przestrzegając przy tym kilku określonych zasad.

Oto początkowe ustawienie układanki:

Problem z Wieżą Hanoi

A oto ostateczny cel:

Regulamin Wieży Hanoi

Oto podstawowe zasady Wieży Hanoi:

Na początku układanki wszystkie dyski ułożone są na pręcie pierwszym.
W stanie końcowym wszystkie dyski z pręta pierwszego układane są na pręcie drugim lub trzecim.
W danym momencie tylko jeden dysk może przenieść się z jednego pręta na drugi.
Można przesuwać tylko najwyżej położony krążek na pręcie.
Dysku nie można położyć na mniejszym dysku.

Oryginalna legenda mówiła o przesunięciu 64 dysków. Kapłani mogli przesuwać po jednym dysku na raz, zgodnie z zasadami. Według legendy istniała przepowiednia, że jeśli uda im się dokończyć zadanie, nastąpi koniec świata. W części poświęconej złożoności czasowej pokażemy, że układ Wieży Hanoi z n dyskami wymaga 2^n – 1 ruchu.

Zatem, jeśli kapłani potrzebowali 1 sekundy, aby przesunąć jeden dysk, całkowity czas rozwiązania zagadki wyniósłby 2^64 – 1 sekundy, czyli w przybliżeniu 584 942 417 356 lat, 26 dni, 7 godzin i 15 sekund.

Algorytm dla Wieży Hanoi

Najczęstszym sposobem rozwiązania Wieży Hanoi jest algorytm rekurencyjny. Najpierw wybieramy dwa pręty jako źródło i cel; kołek zapasowy pełni funkcję pomocniczą.

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.
Przenieś n-ty dysk z kołka źródłowego na kołek docelowy.
Przenieś pozostałe n-1 dysków z kołka pomocniczego na kołek docelowy.

Uwaga: Jeśli mamy pojedynczy dysk, możemy przenieść go bezpośrednio ze źródła do miejsca docelowego.

Jak rozwiązać zagadkę Wieża Hanoi

Zilustrujmy algorytm dla trzech dysków. Rozważ kołek A jako źródłowy, kołek B jako pomocniczy, a kołek C jako docelowy.

Krok 1) Początkowo wszystkie dyski ułożone są na kołku A.

Na tym etapie: Źródło = Kołek A, Cel = Kołek C, Pomocnik = Kołek B.

Teraz musimy przenieść górne dyski n-1 ze źródła do pomocniczego.

Uwaga: Mimo że możemy przenieść tylko jeden dysk na raz, krok ten redukuje nasz problem z 3 dyskami do problemu z 2 dyskami, który jest obsługiwany przez wywołanie rekurencyjne.

Krok 2) Wykonując wywołanie rekurencyjne z kołka A, mając kołek B jako miejsce docelowe, używamy kołka C jako pomocniczego.

Zauważ, że wracamy do etapu pierwszego tego samego problemu Wieży Hanoi, ale tym razem dla dwóch dysków. Przenosimy n-1 (czyli jeden) dysk ze źródła do pomocniczego, co powoduje przeniesienie najmniejszego dysku z kołka A na kołek C.

Na tym etapie: Źródło = kołek A, Cel = kołek B, Pomocnik = kołek C.

Krok 3) Zgodnie z algorytmem n-ty (2.) dysk jest teraz przenoszony do miejsca docelowego, kołka B.

Na tym etapie: Źródło = kołek A, Cel = kołek B, Pomocnik = kołek C.

Krok 4) Teraz przenosimy dysk n-1 (dysk pierwszy) z kołka pomocniczego C na kołek docelowy B, wykonując trzeci etap algorytmu.

Na tym etapie: Źródło = kołek A, Cel = kołek B, Pomocnik = kołek C.

Krok 5) Po zakończeniu wywołania rekurencyjnego wracamy do poprzednich ustawień z pierwszego etapu algorytmu.

Krok 6) W drugim etapie przenosimy dysk 3 z kołka źródłowego A na kołek docelowy C.

Na tym etapie: Źródło = kołek A, Cel = kołek C, Pomocnik = kołek B.

Krok 7) Następnym zadaniem jest przeniesienie pozostałych dysków z kołka pomocniczego (kołek B) na kołek docelowy (kołek C). Tym razem jako kołka pomocniczego użyjemy oryginalnego źródła (kołek A).

Krok 8) Ponieważ nie możemy przenieść dwóch dysków jednocześnie, wykonujemy rekurencyjne wywołanie dla dysku 1. Zgodnie z naszym algorytm, miejscem docelowym w tym kroku jest kołek A.

Na tym etapie: Źródło = kołek B, Cel = kołek A, Pomocnik = kołek C.

Krok 9) Nasze wywołanie rekurencyjne zostało zakończone. Przenosimy teraz dysk 2 ze źródła do miejsca docelowego.

Na tym etapie: Źródło = kołek B, Cel = kołek C, Pomocnik = kołek A.

Krok 10) Na koniec przenosimy pozostały dysk n-1 (dysk 1) z dysku pomocniczego do docelowego.

Na tym etapie: Źródło = kołek A, Cel = kołek C, Pomocnik = kołek B.

Rzekomy Code dla 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;
}

Wyjście:

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:

Wracając do algorytmu, wykonujemy rekurencyjne wywołanie dla (n-1) dysków dwa razy na każde wywołanie. Każda (n-1) rekurencja rozpada się na ((n-1)-1) rekurencji i tak dalej, aż dotrzemy do przypadku bazowego z pojedynczym dyskiem.

Dla trzech dysków:

Dysk 3 wywołuje funkcję rekurencyjną dla dysku 2 dwukrotnie.
Dysk 2 wywołuje funkcję rekurencyjną dla dysku 1 dwukrotnie.
Dysk 1 porusza się w stałym czasie, co daje czas na rozwiązanie problemu dla trzech dysków.

Wyrażone jako rekurencja:

= 2 × (Czas rozwiązania dla dwóch dysków) + stały czas przeniesienia dysku 3

= 2 × (2 × czas rozwiązania dla jednego dysku + stały czas przeniesienia dysku 2) + stały czas przeniesienia dysku 3

= (2 × 2) × stały czas przeniesienia dysku 1 + 2 × stały czas przeniesienia dysku 2 + stały czas przeniesienia dysku 3

Dla n dysków wygląda to następująco:

2^n-1 × stały czas przenoszenia dysku 1 + 2^n-2 × stały czas przeniesienia dysku 2 + ….

Ta progresja geometryczna sumuje się do O(2ⁿ – 1), co upraszcza O (2ⁿ), wykładnicza złożoność czasowa.

2) Złożoność przestrzenna:

Złożoność przestrzenna Wieży Hanoi wynosi O(n). Rekursja korzysta ze stosu wywołań, a maksymalna głębokość stosu wynosi n, czyli liczbę dysków. Dlatego złożoność przestrzenna wynosi O(n).

FAQ

Algorytm Wieży Hanoi to rekurencyjna procedura, która przenosi n dysków z kołka źródłowego na kołek docelowy przy użyciu jednego kołka pomocniczego i nigdy nie umieszcza większego dysku na mniejszym.

Minimalna liczba ruchów dla n dysków wynosi 2^n – 1. Trzy dyski wymagają 7 ruchów, cztery dyski wymagają 15 ruchów, a dziesięć dysków wymaga 1,023 ruchów.

Złożoność czasowa wynosi O(2^n), ponieważ każdy dodatkowy dysk podwaja pracę. Rekurencja T(n) = 2T(n-1) + 1 rozwiązuje równanie 2^n – 1, które jest wykładnicze.

Złożoność przestrzenna wynosi O(n), ponieważ stos wywołań rekurencji przechowuje jedną ramkę dla każdego przetwarzanego dysku. Maksymalna głębokość rekurencji osiąga n, więc zapotrzebowanie na pamięć pomocniczą jest liniowe w stosunku do liczby dysków.

Tak. Rozwiązanie iteracyjne wykorzystuje pętlę z ustalonym schematem: w przypadku ruchów nieparzystych należy cyklicznie zamieniać najmniejszy krążek między kołkami, a w przypadku ruchów parzystych wykonać jedyny dopuszczalny ruch, który nie jest najmniejszym ruchem.

Algorytm uczy rekurencji, modeluje schematy rotacji kopii zapasowych w celu przechowywania danych, steruje sekwencjonowaniem ramienia robota i jest wykorzystywany w testach neuropsychologicznych mierzących zdolność planowania.

Agenci uczący się przez wzmacnianie rozwiązują problem Wieży Hanoi, traktując każdą konfigurację dysku jako stan, a każdy ruch jako akcję. Jest to powszechny punkt odniesienia w planowaniu i hierarchicznym uczeniu się zasad.

Tak. GitHub Copilot, ChatGPT i Gemini generować rekurencyjne rozwiązania Wieży Hanoi w Python, C++, JavaProgramiści powinni nadal weryfikować przypadki bazowe i kolejność argumentów.

Algorytm Wieży Hanoi: Python, C++ Code

Czym jest Wieża Hanoi?

Regulamin Wieży Hanoi

Algorytm dla Wieży Hanoi

Jak rozwiązać zagadkę Wieża Hanoi

Rzekomy Code dla Wieży Hanoi

Kod programu w C++

Kod programu w Python

Złożoność Wieży Hanoi

FAQ

Podsumuj ten post następująco:

Zapisz się do newslettera