Hanoin torni -algoritmi: Python, C++ Code

Mikä on Hanoin torni?

Hanoin torni on matemaattinen pulmapeli, joka koostuu kolmesta sauvasta ja päällekkäin asetellusta pinosta kutistuvia kiekkoja. Se tunnetaan myös Brahman tornina tai Lucasin tornina, koska ranskalainen matemaatikko Edouard Lucas esitteli sen vuonna 1883. Pulmapeli perustuu legendoihin kultakiekkojen siirtämisestä kolmen sauvan välillä.

Tässä pulmapelissä on kolme tankoa ja vaihteleva määrä pinottuja kiekkoja. Tangot on järjestetty syklisiksi torneiksi siten, että suuremmat kiekot ovat pinossa pohjalla ja pienemmät päällekkäin.

Aluksi meille annetaan kolme tappia tai tankoa. Yhteen niistä (esimerkissä tappiin A) kaikki kiekot on pinottu. Tavoitteena on siirtää koko pino tangosta (A) toiseen (C) noudattaen muutamia erityisiä sääntöjä.

Tässä on palapelin alustava kokoonpano:

Hanoin torni -ongelma

Ja tämä on lopullinen tavoite:

Hanoin tornin säännöt

Tässä ovat Hanoin tornin tärkeimmät säännöt:

• Palapelin alkutilassa kaikki kiekot on pinottu ensimmäiselle tangolle.
• Lopullisessa tilassa kaikki ensimmäisen tangon kiekot pinotaan toisen tai kolmannen tangon päälle.
• Vain yksi kiekko voi kerrallaan siirtyä sauvasta toiseen.
• Vain tangon ylintä kiekkoa voi liikuttaa.
• Levyä ei voi asettaa pienemmän levyn päälle.

Alkuperäisessä legendassa kerrottiin 64 kiekon siirtämisestä. Papit saivat sääntöjen mukaan siirtää yhden kiekon kerrallaan. Legendan mukaan oli ennustus, että maailma loppuisi, jos he saisivat teon suoritettua. Aikavaativuusosiossa osoitamme, että n kiekon sisältävä Hanoin torni -pelimuoto vaatii 2^n – 1 siirtoa.

Jos papit siis tarvitsivat yhden sekunnin yhden kiekon siirtämiseen, kokonaisaika pulman ratkaisemiseen olisi 2^64 – 1 sekuntia eli noin 584 942 417 356 vuotta, 26 päivää, 7 tuntia ja 15 sekuntia.

Algoritmi Tower of Hanoin

Yleisin tapa ratkaista Hanoin torni on rekursiivinen algoritmi. Ensin valitaan kaksi sauvaa lähteeksi ja kohteeksi; ylimääräinen tappi toimii apu- tai apuna.

Tässä on vaiheet Hanoin tornin ratkaisemiseksi:

• Siirrä ylimmät n-1-levyt lähdenastasta aputappiin.
• Siirrä n:s kiekko lähdetapista kohdetappiin.
• Siirrä jäljellä olevat n-1 kiekkoa aputapista kohdetappiin.

Huomautus: Jos meillä on yksi levy, voimme siirtää sen suoraan lähteestä kohteeseen.

Kuinka ratkaista Tower of Hanoi -pulma

Havainnollistetaan algoritmia kolmelle levylle. Tarkastellaan tappi A:ta lähteenä, tappi B:tä apulevynä ja tappi C:tä määränpäänä.

Vaihe 1) Aluksi kaikki kiekot pinotaan tapille A.

Tässä vaiheessa: Lähde = tappi A, Määränpää = tappi C, Auttaja = tappi B.

Nyt meidän on siirrettävä parhaat n-1 levyt lähteestä avustajalle.

Huomautus: Vaikka voimme siirtää vain yhden levyn kerrallaan, tämä vaihe supistaa kolmen levyn ongelman kahden levyn ongelmaksi, joka käsitellään rekursiivisella kutsulla.

Vaihe 2) Kun teemme rekursiivisen kutsun tapista A ja määränpäänä tapista B, käytämme tappia C apuobjektina.

Huomaa, että olemme takaisin vaiheessa yksi samassa Hanoin tornin ongelmassa, mutta nyt kahden levyn osalta. Siirrämme n-1 (eli yhden) levyn lähteestä apulevyyn, joka siirtää pienimmän levyn tapista A tapiin C.

Tässä vaiheessa: Lähde = tappi A, Määränpää = tappi B, Auttaja = tappi C.

Vaihe 3) Algoritmin mukaan n:s (toinen) levy siirretään nyt kohteeseen, tappiin B.

Tässä vaiheessa: Lähde = tappi A, Määränpää = tappi B, Auttaja = tappi C.

Vaihe 4) Siirrämme nyt n-1-levyn (levy yksi) aputapista C kohdetappiin B algoritmin kolmannen vaiheen mukaisesti.

Tässä vaiheessa: Lähde = tappi A, Määränpää = tappi B, Auttaja = tappi C.

Vaihe 5) Rekursiivisen kutsun jälkeen palaamme algoritmin ensimmäisessä vaiheessa aiemmin käyttämiimme asetuksiin.

Vaihe 6) Toisessa vaiheessa siirrämme levyn 3 lähdetapista A kohdetappiin C.

Tässä vaiheessa: Lähde = tapin A, Määränpää = tapin C, Auttaja = tapin B.

Vaihe 7) Seuraava tehtävä on siirtää jäljellä olevat levykkeet apulevystä (peg B) kohteeseen (peg C). Tällä kertaa käytämme alkuperäistä lähdelevyä (peg A) apulevynä.

Vaihe 8) Koska emme voi siirtää kahta levyä samanaikaisesti, teemme rekursiivisen kutsun levylle 1. Seurauksemme mukaan algoritmi, tämän vaiheen määränpää on tappi A.

Tässä vaiheessa: Lähde = tappi B, Määränpää = tappi A, Auttaja = tappi C.

Vaihe 9) Rekursiivinen kutsumme on valmis. Siirrämme nyt levyn 2 lähteestä määränpäähän.

Tässä vaiheessa: Lähde = tappi B, Määränpää = tappi C, Auttaja = tappi A.

Vaihe 10) Lopetamme siirtämällä jäljellä olevan n-1 levyn (levy 1) apulevyltä määränpäähän.

Tässä vaiheessa: Lähde = tapin A, Määränpää = tapin C, Auttaja = tapin B.

Pseudo Code Hanoin tornille

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

Ohjelmakoodi sisään 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;
}

lähtö:

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

Ohjelmakoodi sisään 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')

lähtö:

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

Hanoin tornin monimutkaisuus

Tässä on Hanoin tornin aika-avaruuskompleksisuus:

1) Aika monimutkaisuus:

Tarkastellaanpa algoritmia uudelleen, teemme rekursiivisen kutsun (n-1) levylle kahdesti kutsua kohden. Jokainen (n-1) rekursio jakautuu ((n-1)-1) rekursioon ja niin edelleen, kunnes saavutamme yhden levyn perustapauksen.

Kolmelle levylle:

• Levy 3 kutsuu levyn 2 rekursiivista funktiota kahdesti.
• Levy 2 kutsuu levyn 1 rekursiivista funktiota kahdesti.
• Levy 1 liikkuu vakioajassa, mikä antaa aikaa ratkaista kolme levyä.

Ilmaistuna toistumisena:

= 2 × (Kahden levyn ratkaisuaika) + levyn 3 siirtämiseen kuluva vakioaika

= 2 × (2 × yhden levyn ratkaisuaika + levyn 2 siirtämiseen tarvittava vakioaika) + levyn 3 siirtämiseen tarvittava vakioaika

= (2 × 2) × levyn 1 liikuttamiseen tarvittava vakioaika + 2 × levyn 2 liikuttamiseen tarvittava vakioaika + levyn 3 liikuttamiseen tarvittava vakioaika

n levylle tästä tulee:

2^n-1 × vakioaika levyn 1 + 2 siirtämiseen^n-2 × vakioaika levyn 2 siirtämiseen + ….

Tämä geometrinen jono summautuu O(2ⁿ – 1), joka yksinkertaistuu muotoon O (2ⁿ), eksponentiaalinen aikakompleksisuus.

2) Avaruuden monimutkaisuus:

Hanoin tornin avaruuskompleksisuus on O(n). Rekursio käyttää kutsupinoa, ja pinon maksimisyvyys on n, levyjen lukumäärä. Siksi avaruuskompleksisuus on O(n).

UKK