hanoi
Consideram ca avem 3 stalpi
(numerotati 1, 2, 3) si 2N discuri. N
discuri sunt albe si au dimensiunile diametrelor distincte, cuprinse intre 1
si N. Celelalte N discuri sunt
negre si au de asemenea dimensiunile diametrelor distincte, cuprinse intre 1
si N. Aceste discuri sunt asezate
pe primii 2 stalpi (N pe stalpul 1 si N pe stalpul 2), in ordine strict descrescatoare
a dimensiunii diametrelor, in culori alternante.
De exemplu pentru N = 3 pe primul stalp vom avea (de jos in sus): discul de
dimensiune 3 alb, discul de dimensiune 2 negru, discul de dimensiune 1 alb.
Iar pe stalpul 2: discul de dimensiune 3 negru, discul de dimensiune 2 alb si
discul de dimensiune 1 negru.
Mutarile permise sunt mutarea unui disc din varful unui stalp pe alt stalp (tot
in varf), cu conditia ca discul peste care se muta sa aiba dimensiune cel putin
egala cu a celui mutat. Intrucat exista cate 2 discuri de aceeasi dimensiune,
acestea pot fi puse oricum unul peste altul.
Cerinta
Scrieti un program care sa determine un sir de mutari dupa a caror executare pe un stalp sa se afle N discuri albe, pe unul N discuri negre, iar unul sa fie gol.
Date de intrare
Pe prima linie a fisierului de intrare hanoi.in este scris N.
Date de iesire
Fisierul hanoi.out va
contine o succesiune de mutari, cate o mutare pe linie. O mutare este descrisa
de o pereche de numere naturale separate printr-un spatiu; primul numar este
stalpul de pe care se ia discul, iar al doilea numar este stalpul pe care se
pune discul. Aceste doua numere pot fi numai 1, 2 sau 3.
Pe ultima linie a fisierului de iesire va fi trecut numarul 0, care semnifica
terminarea mutarilor.
Restrictii
Exemplu
|
hanoi.in |
hanoi.out |
|
2 |
2 3 |
Timp maxim de executie/test: 0.5 secunde
student Marius Andrei
Facultatea de Automatica si Calculatoare
Contact: marsamg@yahoo.com