Algoritam kule Hanoi: Python, C++ Code

⚡ Pametni sažetak

Algoritam Hanojske kule je klasična rekurzivna zagonetka koja pomiče hrpu diskova između tri klina, a da pritom nikada ne stavlja veći disk na manji, što jasno ilustrira princip "zavadi pa vladaj".

🗼 Postavljanje slagalice: Tri klina i n diskova naslaganih u smanjenoj veličini na izvornom klinu, čekaju da budu premješteni na odredišni klin pomoću pomoćnog klina.
📜 Pravila: Samo se jedan disk pomiče u isto vrijeme, može se pomicati samo gornji disk bilo kojeg klina, a veći disk ne može ležati na manjem disku.
🔁 Rekurzivna ideja: Premjestite n-1 diskova na pomoćni klin, premjestite najveći disk na odredišni klin, a zatim premjestite n-1 diskova s pomoćnog klina na odredište.
🇧🇷 Složenost vremena: Rješavanje n diskova zahtijeva 2^n – 1 poteza, što daje eksponencijalnu vremensku složenost od O(2^n) koja vrlo brzo raste s povećanjem n.
🧠 Složenost prostora: Rekurzijski stog može istovremeno pohraniti do n okvira, tako da je prostorna složenost rekurzivnog rješenja O(n).
🛠️ Primjena: Poučavanje rekurzije, shema rotacije sigurnosnih kopija, premještanja podataka temeljenog na stogu, robotskog sekvenciranja i razumijevanja dizajna algoritma "zavadi pa vladaj".

Pročitaj više

Što je toranj u Hanoju?

Hanojski toranj je matematička zagonetka koja se sastoji od tri štapa i snopa diskova sve manje veličine postavljenih jedan na drugi. Poznat je i kao Brahmin toranj ili Lucasov toranj, budući da ga je francuski matematičar Edouard Lucas predstavio 1883. godine. Zagonetka se temelji na legendama o pomicanju zlatnih diskova između tri štapa.

Ova zagonetka ima tri štapa i promjenjiv broj naslaganih diskova. Štapovi su raspoređeni kao ciklički tornjevi, tako da su veći diskovi naslagani na dnu, a manji diskovi na vrhu.

U početku imamo tri klina ili šipke. Na jednoj od njih (klina A u primjeru) složeni su svi diskovi. Cilj je premjestiti cijeli snop s jedne šipke (A) na drugu (C) poštujući nekoliko specifičnih pravila.

Evo početne postavke slagalice:

Problem kule u Hanoju

I ovo je konačni cilj:

Pravila tornja u Hanoju

Evo osnovnih pravila za Hanojski toranj:

U početnom stanju slagalice, svi diskovi su složeni na štap jedan.
U konačnom stanju, svi diskovi s prve šipke složeni su na drugu ili treću šipku.
Samo jedan disk se može pomicati s jedne šipke na drugu u bilo kojem trenutku.
Samo se gornji disk na šipki može pomicati.
Disk se ne može postaviti na manji disk.

Izvorna legenda govorila je o pomicanju 64 diska. Svećenici su mogli pomicati jedan disk odjednom prema pravilima. Prema legendi, postojalo je proročanstvo da će svijet propasti ako uspiju dovršiti čin. U odjeljku o vremenskoj složenosti pokazat ćemo da postavka Hanojske kule od n diskova zahtijeva 2^n – 1 poteza.

Dakle, ako bi svećenicima trebala 1 sekunda za pomicanje jednog diska, ukupno vrijeme za rješavanje zagonetke bilo bi 2^64 – 1 sekunda, ili otprilike 584,942,417,356 godina, 26 dana, 7 sati i 15 sekundi.

Algoritam za Hanojski toranj

Najčešći način rješavanja Hanojskog tornja je rekurzivni algoritam. Prvo, biramo dva štapa kao izvor i odredište; rezervni klin djeluje kao pomoćni ili pomagač.

Evo koraka za rješavanje zagonetke Hanojskog tornja:

Pomaknite gornjih n-1 diskova s izvornog klina na pomoćni klin.
Premjesti n-ti disk s izvornog klina na odredišni klin.
Premjestite preostalih n-1 diskova s pomoćnog klina na odredišni klin.

Bilješka: Ako imamo jedan disk, možemo ga premjestiti izravno od izvora do odredišta.

Kako riješiti zagonetku Tower of Hanoi

Ilustrirajmo algoritam za tri diska. Razmotrimo klin A kao izvor, klin B kao pomoćnik i klin C kao odredište.

Korak 1) U početku su svi diskovi složeni na klin A.

U ovoj fazi: Izvor = Peg A, Odredište = Peg C, Pomoćnik = Peg B.

Sada moramo premjestiti gornjih n-1 diskova iz izvora u pomoćnik.

Bilješka: Iako možemo pomicati samo jedan disk odjednom, ovaj korak svodi naš problem s 3 diska na problem s 2 diska, koji se rješava rekurzivnim pozivom.

Korak 2) Dok vršimo rekurzivni poziv iz pega A s pegom B kao odredištem, koristimo peg C kao pomoćnika.

Primijetite da smo se vratili u prvu fazu za isti problem Hanojske kule, ali sada za dva diska. Pomičemo n-1 (tj. jedan) disk od izvora do pomoćnika, što pomiče najmanji disk s klina A na klin C.

U ovoj fazi: Izvor = peg A, Odredište = peg B, Pomoćnik = peg C.

Korak 3) Prema algoritmu, n-ti (2.) disk se sada prenosi na odredište, peg B.

U ovoj fazi: Izvor = peg A, Odredište = peg B, Pomoćnik = peg C.

Korak 4) Sada premještamo n-1 disk (disk jedan) s pomoćnog klina C na odredišni klin B, slijedeći treću fazu algoritma.

U ovoj fazi: Izvor = peg A, Odredište = peg B, Pomoćnik = peg C.

Korak 5) Nakon završetka rekurzivnog poziva, vraćamo se na prethodnu postavku iz prve faze algoritma.

Korak 6) U drugoj fazi, premještamo disk 3 s izvornog klina A na odredišni klin C.

U ovoj fazi: Izvor = peg A, Odredište = peg C, Pomoćnik = peg B.

Korak 7) Sljedeći zadatak je premjestiti preostale diskove iz pomoćnika (kolica B) u odredište (kolica C). Ovaj put ćemo koristiti originalni izvor (kolica A) kao pomoćnika.

Korak 8) Budući da ne možemo pomicati dva diska odjednom, rekurzivno pozivamo za disk 1. Prema našem algoritam, odredište u ovom koraku je klin A.

U ovoj fazi: Izvor = peg B, Odredište = peg A, Pomoćnik = peg C.

Korak 9) Naš rekurzivni poziv je završen. Sada premještamo disk 2 iz izvora u odredište.

U ovoj fazi: Izvor = peg B, Odredište = peg C, Pomoćnik = peg A.

Korak 10) Završavamo premještanjem preostalog n-1 diska (disk 1) iz pomoćnog uređaja u odredište.

U ovoj fazi: Izvor = peg A, Odredište = peg C, Pomoćnik = peg B.

Nadimak Code za Hanojski toranj

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

Programski kod u 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;
}

Izlaz:

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

Programski kod u 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')

Izlaz:

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

Složenost Hanojskog tornja

Evo vremenske i prostorne složenosti Hanojskog tornja:

1) Vremenska složenost:

Osvrćući se na algoritam, dva puta po pozivu izvršavamo rekurzivni poziv za (n-1) diskova. Svaka (n-1) rekurzija se rastavlja na ((n-1)-1) rekurzija i tako dalje, sve dok ne dođemo do osnovnog slučaja s jednim diskom.

Za tri diska:

Disk 3 dva puta poziva rekurzivnu funkciju za disk 2.
Disk 2 dva puta poziva rekurzivnu funkciju za disk 1.
Disk 1 se kreće u konstantnom vremenu, što daje vrijeme za rješavanje za tri diska.

Izraženo kao ponavljanje:

= 2 × (Vrijeme rješavanja za dva diska) + konstantno vrijeme pomicanja diska 3

= 2 × (2 × vrijeme rješavanja za jedan disk + konstantno vrijeme pomicanja diska 2) + konstantno vrijeme pomicanja diska 3

= (2 × 2) × konstantno vrijeme pomicanja diska 1 + 2 × konstantno vrijeme pomicanja diska 2 + konstantno vrijeme pomicanja diska 3

Za n diskova, ovo postaje:

2^n-1 × konstantno vrijeme za pomicanje diska 1 + 2^n-2 × konstantno vrijeme za pomicanje diska 2 + ….

Ova geometrijska progresija se zbraja u O(2ⁿ – 1), što se pojednostavljuje na O(2ⁿ), eksponencijalna vremenska složenost.

2) Složenost prostora:

Prostorna složenost Hanojskog tornja je O(n). Rekurzija koristi stog poziva, a maksimalna dubina stoga jednaka je n, broju diskova. Zato je prostorna složenost O(n).

Pitanja i odgovori

Algoritam Hanojskog tornja je rekurzivni postupak koji premješta n diskova s izvornog na odredišni disk koristeći jedan pomoćni disk, pri čemu se nikada ne stavlja veći disk na manji.

Minimalni broj poteza za n diskova je 2^n – 1. Tri diska trebaju 7 poteza, četiri diska trebaju 15, a deset diskova trebaju 1,023 poteza.

Vremenska složenost je O(2^n) jer svaki dodatni disk udvostručuje rad. Rekurentna jednadžba T(n) = 2T(n-1) + 1 rješava se na 2^n – 1, što je eksponencijalno.

Prostorna složenost je O(n) jer rekurzijski stog poziva sadrži jedan okvir za svaki disk koji se obrađuje. Maksimalna dubina rekurzije doseže n, pa je potrebna pomoćna memorija linearna s brojem diskova.

Da. Iterativno rješenje koristi petlju s fiksnim uzorkom: na neparnim potezima ciklički se zamjenjuje najmanji disk između klinova, a na parnim potezima se izvodi jedini dopušteni potez koji nije najmanji.

Algoritam podučava rekurziju, modelira sheme rotacije sigurnosnih kopija za pohranu, vodi sekvenciranje robotske ruke i pojavljuje se u neuropsihološkim testovima koji mjere sposobnost planiranja.

Agenti za učenje s potkrepljenjem rješavaju Tower of Hanoi tretirajući svaku konfiguraciju diska kao stanje, a svaki potez kao akciju. To je uobičajena referentna vrijednost za planiranje i hijerarhijsko učenje politika.

Da. GitHub Copilot, ChatGPT i Gemini generirati rekurzivna rješenja Hanojske kule u Python, C++i JavaRazvojni programeri i dalje trebaju provjeriti osnovne slučajeve i redoslijed argumenata.

Algoritam kule Hanoi: Python, C++ Code

Što je toranj u Hanoju?

Pravila tornja u Hanoju

Algoritam za Hanojski toranj

Kako riješiti zagonetku Tower of Hanoi

Nadimak Code za Hanojski toranj

Programski kod u C++

Programski kod u Python

Složenost Hanojskog tornja

Pitanja i odgovori

Sažmite ovu objavu uz:

Prijavite se za bilten