Hanoi

[•TheNechiz]

Problema propusa de Eduard Lucas în 1883 ramane celebra,Turnurile de Hanoi fiind o problemă clasica pentru Divide et Impera.

Problema consta in mutarea discurilor pe tija 2 prin intermediul tijei 3, cu următoarele restrictii:
la fiecare mutare se deplaseaza un singur disc;
discurile se mută numai de pe o tijă pe alta;
un disc cu diametru mai mare nu poate fi asezat peste un disc cu diametru mai mic.

Pentru n = 1 , mutam discul pe ultima tije
Pentru n = 2 ,se fac mutarile 1 → 3, 1 →  2, 3 →  2.
In cazul in care n>3 problema se complica. Notam cu Hanoi(n,1,2,3) sirul mutarilor celor n discuri de pe tija 1 pe tija 2 , utilizand ca tija intermediara, tija 3.
Conform strategiei Divide et impera incercam sa descompunem problema in alte doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor. In acest sens, observam ca mutarea celor n discuri de pe tija 1 pe tija 2,utilizand ca tija intermediara tija 3, este echivalenta cu:
mutarea a n-1 discuri de pe tija 1 pe tija 3 , utilizand ca tija intermediara tija 2;
mutarea discului ramas pe tija 1 pe tija 2;
mutarea a n-1 discuri de pe tija 3 pe tija 2 , utilizand ca tija intermediara tija 1.

Din cele de mai sus putem determina foarte usor relatia de recurenta si sa scriem un program care sa afiseze mutarile pe care trebuie sa le efectuam.

Încerc de ceva timp să rezolv problema pentru un numar variabil de tije,înca nu am reusit nimic.
Va rog,poate cineva sa ma ajute cu o idee ,un sfat...orice.

[•razvan.popa]

Problema turnurilor din Hanoi (varianta generalizata s-a dat la Facebook Challenge - https://facebook.interviewstreet.com/recruit/challenges) - trebuia sa ajungi de la o configuratie initiala la una finala in numar minim de pasi.

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5

Eu am rezolvat-o cu un BFS pe configuratii - maxim 5^8 stari (le poti memora pe biti si pune intr-un set). Ca si complexitate ar fi O(K^N * log(K^N))...eventual cu niste hashuri poti scapa de log. Nu stiu daca exista complexitati mai bune, eu cu asta am luat punctaj maxim.

[•wefgef]

http://acm.sgu.ru/problem.php?contest=0&problem=202

Solutia acceptata este o dinamica, desi din cate stiu inca nu a reusit nimeni sa-i demonstreze corectitudinea.