Hanoi torni algoritm: Python, C++ Code

Autor: Sarah Chen Sarah Chen
Hours Ajakohastatud

⚡ Nutikas kokkuvõte

Hanoi torni algoritm on klassikaline rekursiivne mõistatus, mis liigutab kettavirna kolme pulga vahel, asetamata kunagi suuremat ketast väiksema peale, illustreerides selgelt jaga-ja-valitse-põhimõtteid.

  • 🗼 Mõistatuse seadistamine: Kolm pulka ja n ketast on kahaneva suurusega virnastatud lähtepulgale, oodates abipulga abil sihtpulgale liigutamist.
  • 📜 Reeglid: Korraga liigub ainult üks ketas, liikuda saab ainult iga pulga ülemine ketas ja suurem ketas ei saa toetuda väiksemale kettale.
  • 🔁 Rekursiivne idee: Liiguta n-1 ketast abipulgale, liiguta suurim ketas sihtpulgale ja seejärel liiguta n-1 ketast abipulgalt sihtpunkti.
  • ️ Aja keerukus: n ketta lahendamine nõuab 2^n – 1 käiku, mis annab eksponentsiaalse O(2^n) ajalise keerukuse, mis kasvab n suurenedes väga kiiresti.
  • 🧠 Ruumi keerukus: Rekursioonipinu mahutab korraga kuni n kaadrit, seega on rekursiivse lahenduse ruumikeerukus O(n).
  • 🛠️ Rakendused: Rekursiooni, varukoopiate rotatsiooniskeemide, pinupõhise andmete liikumise, robootikapõhise järjestamise ja jaga-ja-valitse algoritmide disaini mõistmise õpetamine.
Loe rohkem

Hanoi torni algoritm

Mis on Hanoi torn?

Hanoi torn on matemaatiline pusle, mis koosneb kolmest vardast ja üksteise peale asetatud väheneva suurusega ketaste virnast. Seda tuntakse ka Brahma torni või Lucase tornina, kuna prantsuse matemaatik Edouard Lucas tutvustas seda 1883. aastal. Pusle põhineb legendidel kuldketaste liigutamisest kolme varda vahel.

Sellel puslel on kolm varrast ja muutuv arv virnastatud kettaid. Vardad on paigutatud tsükliliste tornidena, nii et suuremad kettad on virnastatud alla ja väiksemad kettad peale.

Alguses on meile antud kolm pulka või varrast. Ühele neist (näites pulk A) on kõik kettad virnastatud. Eesmärk on liigutada kogu virn ühelt vardast (A) teisele (C), järgides samal ajal mõnda kindlat reeglit.

Siin on pusle esialgne ülesehitus:

Hanoi torni probleem

Hanoi torni probleem

Ja see ongi lõppeesmärk:

Hanoi torn

Hanoi torni reeglid

Siin on Hanoi torni peamised reeglid:

  • Pusle algseisus on kõik kettad virnastatud ühele vardale.
  • Lõppseisundis on kõik esimese varda kettad virnastatud teisele või kolmandale vardale.
  • Igal ajahetkel saab ühelt vardast teisele liikuda ainult üks ketas.
  • Liigutada saab ainult varda kõige ülemist ketast.
  • Ketast ei saa väiksema ketta peale asetada.

Algupärane legend rääkis 64 ketta liigutamisest. Preestrid said reeglite kohaselt korraga ühte ketast liigutada. Legendi järgi oli ennustus, et kui nad suudavad selle teo lõpule viia, tuleb maailmalõpp. Aja keerukuse osas näitame, et n kettaga Hanoi torni seadistamine nõuab 2^n – 1 käiku.

Seega, kui preestritel kuluks ühe ketta liigutamiseks 1 sekund, oleks mõistatuse lahendamise koguaeg 2^64 – 1 sekundit ehk umbes 584 942 417 356 aastat, 26 päeva, 7 tundi ja 15 sekundit.

Hanoi torni algoritm

Hanoi torni lahendamiseks kasutatakse kõige levinumat rekursiivset algoritmi. Esmalt valime allikaks ja sihtkohaks kaks varrast; varutihvt toimib abivartena.

Siin on sammud Hanoi torni mõistatuse lahendamiseks:

  • Liigutage ülemised n-1 kettad lähtepulgalt abipulgale.
  • Liiguta n-ndat ketast lähtepulgalt sihtpulgale.
  • Liiguta ülejäänud n-1 ketast abipulgalt sihtpulgale.

Märge: Kui meil on üks ketas, saame selle otse allikast sihtkohta teisaldada.

Kuidas lahendada Hanoi torni mõistatus

Illustreerime algoritmi kolme ketta jaoks. Vaatleme pulka A allikana, pulka B abikettana ja pulka C sihtkettana.

Step 1) Algselt on kõik kettad virnastatud pulgale A.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk A, Sihtkoht = pulk C, Abiline = pulk B.

Nüüd peame ülemised n-1 kettad allikast abistajasse teisaldama.

Märge: Kuigi korraga saab liigutada ainult ühte ketast, taandab see samm meie 3 ketta probleemi 2 ketta probleemiks, mida käsitletakse rekursiivse kutse abil.

Step 2) Kuna me teeme rekursiivse kutse pesast A, kus sihtkohaks on pesa B, siis kasutame abimehena pesa C.

Pane tähele, et oleme tagasi sama Hanoi torni probleemi esimeses etapis, aga nüüd kahe kettaga. Liigutame n-1 (st ühe) ketta lähtekettalt abikettale, mis omakorda liigutab väikseima ketta pulgalt A pulgale C.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk A, Sihtkoht = pulk B, Abimees = pulk C.

Step 3) Algoritmi kohaselt teisaldatakse n-s (teine) ketas nüüd sihtkohta, pulka B.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk A, Sihtkoht = pulk B, Abimees = pulk C.

SEOTUD ARTIKLID

Step 4) Nüüd liigutame n-1 ketta (ketas üks) abipulgalt C sihtpulgale B, järgides algoritmi kolmandat etappi.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk A, Sihtkoht = pulk B, Abimees = pulk C.

Step 5) Pärast rekursiivse kutse lõpetamist naaseme algoritmi esimeses etapis eelmisele seadistusele.

Step 6) Teises etapis liigutame ketta 3 lähtepulgalt A sihtpulgale C.

Selles etapis: Allikas = pulk A, Sihtkoht = pulk C, Abimees = pulk B

Step 7) Järgmine ülesanne on ülejäänud kettad abikettalt (peg B) sihtkohta (peg C) teisaldada. Seekord kasutame abikettana algset allikat (peg A).

Lahenda Hanoi torni mõistatus

Step 8) Kuna me ei saa kahte ketast korraga liigutada, teeme kettale 1 rekursiivse päringu. Meie andmete kohaselt algoritm, on selle sammu sihtkohaks pulk A.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk B, Sihtkoht = pulk A, Abimees = pulk C.

Step 9) Meie rekursiivne kutse on lõppenud. Nüüd liigutame ketta 2 lähtest sihtkohta.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk B, Sihtkoht = pulk C, Abimees = pulk A.

Step 10) Lõpetuseks liigutame ülejäänud n-1 ketta (ketas 1) abikettast sihtkohta.

Lahenda Hanoi torni mõistatus

Selles etapis: Allikas = pulk A, Sihtkoht = pulk C, Abimees = pulk B

Pseudo Code Hanoi torni jaoks

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

Programmi kood sisse 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;
}

Väljund:

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

Programmi kood sisse 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')

Väljund:

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

Hanoi torni keerukus

Siin on Hanoi torni aja ja ruumi keerukus:

1) Aja keerukus:

Algoritmile tagasi vaadates teeme (n-1) kettale rekursiivse väljakutse kaks korda iga väljakutse jooksul. Iga (n-1) rekursioon jaguneb ((n-1)-1) rekursiooniks ja nii edasi, kuni jõuame ühe ketta baasjuhtumini.

Kolme ketta puhul:

  • Ketas 3 kutsub ketta 2 rekursiivset funktsiooni kaks korda.
  • Ketas 2 kutsub ketta 1 rekursiivset funktsiooni kaks korda.
  • Ketas 1 liigub konstantse aja jooksul, andes aega kolme ketta lahendamiseks.

Väljendatud korduvusena:

= 2 × (kahe ketta lahendamise aeg) + ketta 3 liigutamiseks kuluv konstantne aeg

= 2 × (2 × ühe ketta lahendamise aeg + ketta 2 liigutamise konstantne aeg) + ketta 3 liigutamise konstantne aeg

= (2 × 2) × ketta 1 liigutamise konstantne aeg + 2 × ketta 2 liigutamise konstantne aeg + ketta 3 liigutamise konstantne aeg

n ketta puhul saab sellest järgmine tulemus:

2n-1 × ketta 1 + 2 liigutamiseks kuluv konstantne aegn-2 × ketta 2 liigutamise konstantne aeg + ….

See geomeetriline progressioon summastub O(2n – 1), mis lihtsustub kujule O(2n), eksponentsiaalne ajaline keerukus.

2) Ruumi keerukus:

Hanoi torni ruumikeerukus on O(n). Rekursioon kasutab väljakutsete pinu ja pinu maksimaalne sügavus võrdub n-ga ehk ketaste arvuga. Seetõttu on ruumikeerukus O(n).

KKK

Hanoi torni algoritm on rekursiivne protseduur, mis liigutab n ketast lähte-pegist siht-pegile ühe abipegi abil, asetades kunagi suuremat ketast väiksema peale.

n ketta minimaalne käikude arv on 2^n – 1. Kolme ketta puhul on vaja 7 käiku, nelja ketta puhul 15 ja kümne ketta puhul 1,023 käiku.

Ajaline keerukus on O(2^n), sest iga täiendav ketas kahekordistab töö. Rekursioon T(n) = 2T(n-1) + 1 laheneb väärtuseks 2^n – 1, mis on eksponentsiaalne.

Ruumi keerukus on O(n), kuna rekursiooniväljakutsete pinu mahutab iga töödeldava ketta kohta ühe kaadri. Maksimaalne rekursioonisügavus ulatub n-ni, seega on vajalik lisamälu lineaarne ketaste arvuga.

Jah. Iteratiivne lahendus kasutab fikseeritud mustriga tsüklit: paaritutel käikudel vahetatakse väikseim ketas tsükliliselt pulkade vahel ja paarisarvulistel käikudel tehakse ainus lubatud mitteväikseim käik.

Algoritm õpetab rekursiooni, modelleerib varundamise rotatsiooniskeeme salvestuseks, juhib robotkäe järjestamist ja esineb neuropsühholoogilistes testides, mis mõõdavad planeerimisvõimet.

Tugevdusõppe agendid lahendavad Hanoi torni probleemi, käsitledes iga ketta konfiguratsiooni olekuna ja iga liigutust toiminguna. See on levinud võrdlusalus planeerimiseks ja hierarhilise poliitika õppimiseks.

Jah. GitHub Copilot, ChatGPT ja Gemini Hanoi torni rekursiivsete lahenduste genereerimine Python, C++ja JavaArendajad peaksid ikkagi kontrollima baasjuhtumeid ja argumentide järjekorda.

Võta see postitus kokku järgmiselt: