HANOJSKE KULE-ALGORITAM

Problem Hanojskih kula je poznat matematičko-algoritamski zadatak iz oblasti rekurzije i kombinatorike.
Problem se sastoji od 3 stubića A,B,C. Na disk A su poređani diskovi tako da je disk najvećeg prečnika na dnu zatim preko njega nešto manjeg, zatim sledećeg još manjeg itd. Dakle ako posmatramo vrednosti prečnika kao brojeve odozdo na više, taj niz brojeva je u opadajućem redosledu.
Cilj ove, možemo da nazovemo igre je da se diskovi premeste na disk C, koristeći pomoćni stub B, poštujući sledeća pravila:
U jednom potezu može se premeštati samo jedan disk.
Nikada se ne sme postaviti veći disk na manji.

Ovaj problem se obično rešava rekurzivno. Ako je samo 1 disk, jednostavno ga premestimo sa A na C.
Ako imamo n diskova, premestimo n-1 diskova sa A na B (pomoću C).

Premestimo najveći disk sa A na C.

Premestimo n-1 diskova sa B na C (pomoću A).

Algoritam se može rešiti rekurzijom.
Uočimo početno stanje diskova i stalaka na slici 1. Na stalku A je poređano n diskova(na slici n=6) od najvećeg(prečnika) ka najmanjem idući odozdo na gore, dakle najmanji disk je na vrhu. Cilj je da se ovi diskovi svi premeste na stalak C u istom redosledu. Premeštanje diska po disk je ograničeno uslovom da se veći disk ne sme naći iznad manjeg. Koristimo pomoćni stalak da privremeno neki od diskova prvo sklonimo tamo, da bi izvukli veči disk i stavili na odredište C.

Slika 1: Problem "Hanojske kule" - početno stanje

Ako bi smo napravili funkciju koja treba da ispiše koji disk se premešta sa kog(izvor) na koji(odredište) i preko kog(pomoćni) to bi izgledalo na primer:tower_of_hanoi(int n, string from, string to, string helper)Ovde treba uočiti da se problem može rešiti tako što se problem svodi na rekurzivno ponavljanjeg sledećeg: Da bi stavili najveći disk(označimo ga kao n-ti) na odredište(stalak C) prvo se mora skloniti ostatak manjih diskova, dakle diskovi od mesta n-1 pa do 1 vidi sliku 2. U primeru na slici 2 pokazano je premeštanje gomile od 4 gornja diska, tj. od n-2 do 1(od isprekidane linije na slici 2). Za preostala dva najveća diska(plava na slici 2), postupak bi se ponavljao na sličan način. Možemo smatrati da je najveći disk gomile koja se premešta žuti disk. Njega treba postaviti prvog na stalak C. Da bi to uradili potrebno je skloniti ostale diskove na pomoćni stalak B.

Početno premeštanje gomile od 4 diska odozgo-Hanojske kule

Slika 2: Početno premeštanje gomile od 4 diska odozgo

Dakle, problem koji rekurzivna funkcija treba da odradi svodi se na sledeće:

Skloniti gomilu diskova koji su iznad trenutno najvećeg(u početku je to n-ti disk) na pomoćni stalak B.(sloka 3)
premeštanje trenutno najvećeg diska(u početku je stvarno najveći, a kako se gomila bude smanjivala, to će biti trenutno največi) direktno na stalak C(slika 4)
Premeštanje ostatka diskova sa B na C(slika 5)

hanojske kule: Premeštanje 3 manja diska odozgo sa A na pomoćni stalak B

Slika 3: Premeštanje 3 manja diska odozgo sa A na pomoćni stalak B

Korak 1: Premeštanje 3 manja diska na stalak B

Ono što je bitno u koraku 1, tj kod premeštanja gomile 3 manja diska je to da se ovo premeštanje ne može odraditi "odjednom", niti jedan po jedan disk direktno na stalak B, jer se ne sme desiti situacija da se disk većeg prečnika naće preko diska manjeg prečnika, već se koristi ista rekurzija, tj. isti postupak od koraka 1, 2 i 3, ali sa stepenom rekurzije za 1 manje. Npr. ako je na početku bilo n=4, sada će največi preostali disk biti na nivou n=3. Postupak će se rekurzivno ponavljati sve dok se svi diskovi ne naću na stalku B.
Ako bi pokrenuli program ovaj opisani korak bi se sveo na sledeće pod korake:
Premeštanje diska 1 sa A na B
Premeštanje diska 2 sa A na C
Premeštanje diska 1 sa B na C
Premeštanje diska 3 sa A na B
Premeštanje diska 1 sa C na A
Premeštanje diska 2 sa C na B
Premeštanje diska 1 sa A na BDisk 1 je najmanji na ovoj gomili, a disk 3 najveći.

Hanojske kule: Premeštanje trenutno najvećeg diskadirektno na stalak C

Slika 4: Premeštanje trenutno najvećeg diskadirektno na stalak C

Korak 2: Premeštanje trenutno najvećeg diskadirektno na stalak C

Kada je gomila od 3 diska sklonjena na stalak B, sada se disk 4 može direktno premestiti sa stalka A na stalak C. U pokrenutom programu to bi odgovaralo sledećem ispisu: Premeštanje diska 4 sa A na C

Premeštanje ostatka diskova sa B na C

Premeštanje preostale gomile od 3 diska sa pomoćnog B na odredišni stalak C, takoće se ne može uraditi u 1 koraku već daljom upotrebom iste rekurzije, sa zamenjenim izvorom, odredištem i pomoćnim stalkom. Pogledajmo nastavak izvršenja programa koji ovo opisuje(vidi sliku 5): Premeštanje diska 1 sa B na C
Premeštanje diska 2 sa B na A
Premeštanje diska 1 sa C na A
Premeštanje diska 3 sa B na C
Premeštanje diska 1 sa A na B
Premeštanje diska 2 sa A na C
Premeštanje diska 1 sa B na C

Slika 5: Premeštanje 3 manja diska sa pomoćnog stalka B na odredišni stalak C

Iz ovoga možemo zaključiti kako bi trebalo da izgleda kod: Napraviti rekurzivnu funkciju, koja za parametre prima tekst(slovo) izvornog, odredišnog i pomoćnog stuba kao i nivo rekurzije n. Sama funkcija prvo proverava trenutni nivo rekurzije i ako je nula, izaziva vraćanje unazad. Ako nije nula poziva se rekurzija (ista funkcija) koja će da napravi niz poziva smanjujući nivo rekurzije svaki put za 1, a to odgovara postupku 1, gde se 3 manja diska premeštaju sa stalka A na pomoćni stalak B.
Zatim se ispisuje tekst u trenutnom nivou rekurzije. To odgovara postupku 2, tj. Premeštanje donjeg diska sa A na odredišni stalak C.
I na kraju još jedan rekurzivni poziv koji će izvršiti postupak 3, odnosno premeštanje gomile diskova sa B na C.

#include <iostream>using namespace std;// Funkcija koja rekurzivno rešava problem Hanojskih kula// n       – broj diskova koje treba premestiti// from    – ime stuba sa koga premeštamo (izvorni stub)// to      – ime stuba na koji premeštamo (ciljni stub)// helper  – ime pomoćnog stubavoidtower_of_hanoi(int n, string from, string to, string helper) {
    // Bazni slučaj: ako nema diskova, nema potezaif (n == 0) {
        return;
    }

    // 1. Premestimo n-1 diskova sa "from" stuba na "helper" stub//    Koristimo "to" stub kao pomoćnitower_of_hanoi(n - 1, from, helper, to);

    // 2. Premestimo najveći (n-ti) disk sa "from" stuba na "to" stubcout << "Premeštanje diska " << n
         << " sa " << from
         << " na " << to << endl;

    // 3. Premestimo n-1 diskova sa "helper" stuba na "to" stub//    Koristimo "from" stub kao pomoćnitower_of_hanoi(n - 1, helper, to, from);
}

intmain() {
    int n;
    cout << "Unesite broj diskova: ";
    cin >> n;

    // Pokrećemo algoritam – želimo da prebacimo sve diskove sa A na C// koristeći B kao pomoćni stubtower_of_hanoi(n, "A", "C", "B");

    return 0;
}

Problem Hanojskih kula – primer i objašnjenje

Primer ulaza:

Primer izlaza:

Premeštanje diska 1 sa A na B
Premeštanje diska 2 sa A na C
Premeštanje diska 1 sa B na C
Premeštanje diska 3 sa A na B
Premeštanje diska 1 sa C na A
Premeštanje diska 2 sa C na B
Premeštanje diska 1 sa A na B
Premeštanje diska 4 sa A na C
Premeštanje diska 1 sa B na C
Premeštanje diska 2 sa B na A
Premeštanje diska 1 sa C na A
Premeštanje diska 3 sa B na C
Premeštanje diska 1 sa A na B
Premeštanje diska 2 sa A na C
Premeštanje diska 1 sa B na C

Objašnjenje koda

Algoritam koristi rekurziju i zasniva se na tri koraka:

Premestiti n−1 diskova sa izvornog stuba (A) na pomoćni stub (B).
Premestiti najveći disk (n-ti) sa izvornog stuba (A) na ciljni stub (C).
Premestiti n−1 diskova sa pomoćnog stuba (B) na ciljni stub (C).

Ovi koraci se rekurzivno ponavljaju dok ne ostane samo jedan disk, što predstavlja bazni slučaj rekurzije.

Ograničenja / kompleksnost

Broj poteza potreban da se reši problem sa n diskova je:

P(n) = 2^n − 1

To znači da broj poteza eksponencijalno raste sa brojem diskova:

n = 3 → 7 poteza
n = 4 → 15 poteza
n = 10 → 1023 poteza
n = 20 → preko milion poteza

Zbog toga se problem koristi kao ilustracija rekurzije i akademski primer, dok je praktično neizvodljivo rešavati ga za velike vrednosti n.