Hanojski stolpi

Iz MaFiRaWiki

Hanoiski stolpi je matematična igra, ki jo je leta 1883 objavil francoski matematik Edouard Lucas. V računalništvu je zgled za uporabo rekuzije in metode deli in vladaj (angl. divide and conquer).

Problem je definiran na naslednji način: imamo n obročev in 3 palice, ki jih označimo z A, B in C. Na začetku so vsi obroči postavljeni na palico A in urejeni po velikosti, tako da je spodaj največji in zgoraj najmanjši. Naloga zahteva, da vse obroče premaknemo na palico C. Pri tem lahko naenkrat premaknemo le en obroč in nikoli ne smemo postaviti večjega obroča na manjšega.

Slika:HanoiskiStolpi.jpg

Poiskati moramo zaporedje premikov z opisanimi omejitvami tako, da bomo vseh n obročev s palice A premaknili na palico C. Problem rešimo z razbitjem na 3 podprobleme - z metodo deli in vladaj.

  1. Če želimo dati največji obroč na palico C, potem mora biti ta prazna, zato vseh n-1 obročev preložimo na palico B.
  2. Največji obroč s palice A preložimo na palico C.
  3. Vseh n-1 obročev preložimo na palico C s pomočjo palice A.

Vsebina

Algoritem

Preloži n obročev z A na C s pomočjo B.
Če je n = 1, potem daj obroč A na C 
sicer
Preloži n-1 obročev z A na B s pomočjo C
Preloži obroč z A na C
Preloži n-1 obročev z B na C s pomočjo A


Koda v Javi

Uporabimo rekurzivno metodo.

  1. public class HanoiStolpi{
  2. public static void main (String[] args){
  3. hanoi(3, 'A', 'B', 'C');
  4. }
  5. public static void hanoi(int n, char A, char B, char C){
  6. if(n == 1){
  7. System.out.println("Prelozi z " + A + " na " + C)
  8. }
  9. else {
  10. hanoi(n-1, A, C, B);
  11. hanoi(1, A, B, C);
  12. hanoi(n-1, B, A, C);
  13. }
  14. }
  15. }

Legenda o hanoiskih stolpih

Obstaja več različic legend o hanoiskih stolpih. Ena izmed njih govori o Brahminem stolpu v Indiji. V hindujskem templju je bila sestavljenka v obliki piramide, ki so jo uporabljali za urjenje mentalnih sposobnosti mladih svečenikov. Legenda pravi, da je bil na začetku v templju sklad iz 64 zlatih obročev, ki so bili zloženi po velikosti, tako da so bili manjši obroči na večjih. Naloga je zahtevala, da vseh 64 obročev z ene od treh palic preložijo na drugo tako, da noben obroč ne bi bil nikoli položen na manjšega. Svečeniki so marljivo delali noč in dan. Takoj ko bi bila opravljena zadnja poteza, naj bi se po starodavni prerokbi tempelj sesul v prah in svet naj bi izginil.

Koliko resnice je v legendi? Število premikov, ki bi jih svečeniki morali opraviti je 264 -1. Če bi delali noč in dan, in če bi vsako sekundo premaknili en obroč, bi potrebovali malo več kot 580 bilijonov let, vesolje pa je staro približno 13,7 bilijonov let.

Glej tudi

Viri

Osebna orodja