hanoi2

Hanoi2

== include(page="template/taskheader" task_id="hanoi2") ==

!{float:right;}problema/hanoi2?infoarena1.png!

Turnurile din Hanoi este un joc matematic. Este format din trei tije şi un număr variabil de discuri, de diferite mărimi, care pot fi poziţionate pe oricare din cele 3 tije. Jocul începe având discurile aşezate în stivă pe prima tijă, în ordinea mărimii lor, astfel încât să formeze un turn. Scopul jocului este acela de a muta întreaga stivă de pe o tijă pe alta, respectând următoarele reguli:
* Doar un singur disc poate fi mutat, la un moment dat.

Gigel este pasionat de informatică. Chiar de aceea, când au învăţat algoritmul turnurilor din Hanoi la şcoală, tatăl său l-a surprins cu un joc Hanoi, constând din trei tije şi mai multe discuri de dimensiuni diferite. Astfel Gigel nu numai că a scris un program ce rezolvă problema, dar poate să şi verifice corectitudinea acestuia.

 
 
 
!{float:right;}problema/hanoi2?infoarena2.png!

Fratele său mai mic, Petrică, dornic să încerce şi el noul joc, s-a apucat să mute discurile pe tijă, fără să ţină cont
de regulile descrise mai sus. Astfel a reuţit să încurce ordinea discurilor. Dar Gigel nu s-a supărat. A inventat
următorul joc:

h2. Date de intrare

Fişierul de intrare $hanoi2.in$ ...
 

Fişierul *hanoi.in* are următoarea structură:
* Pe prima linie un număr natural d. Valori posibile 1, 2 sau 3 şi reprezintă numărul tijei destinaţie, pe care se vor grupa discurile în final în ordinea mărimii lor.

h2. Date de ieşire
Fişierul *hanoi.out* are următoarea structură:

Pe fiecare linie a fişierului se va scrie câte o mutare în ordinea efectuărilor lor. Fiecare mutare constă dintr-o pereche de numere naturale a b cu semnificaţia: „discul din vârful tijei a se mută pe tija b”
Pe ultima linie a fişierului de ieşire se va tipări perechea de numere 0 0.

h2. Exemplu

table(example). |_. hanoi2.in |_. hanoi2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. hanoi2.in |_. hanoi2.out |_. Explicaţie |
| 3
2 3 0
4 7 5 1 9
| 2 3
1 3
2 1
2 3
1 2
1 3
2 3
0 0
| discurile pe cele trei tije sunt:
     *9*
 7    1
 4    5
(1) (2) (3) de la 2 la 3
 
* 7*   1
 4   5   9
(1) (2) (3) de la 2 la 3
 
    * 1*   7
 4   5   9
(1) (2) (3) de la 2 la 3
 
 1       7
 4   *5*   9
(1) (2) (3) de la 2 la 3
 
         5
* 1*       7
 4       9
(1) (2) (3) de la 2 la 3
 
         5
         7
* 4*   1   9
(1) (2) (3) de la 2 la 3
 
         4
         5
         7
    * 1*   9
(1) (2) (3) de la 2 la 3
 
         1
         4
         5
         7
         9
(1) (2) (3) marcaj de sfarsit 0 0
|
 
Următoarele informaţii despre structura fişierelor de intrare vă pot fi utile:
!{display:block; margin-left:auto; margin-right:auto;}problema/hanoi2?infoarena3.png!
 
Semnificaţia simbolurilor este:
 
!{float:left;}problema/hanoi2?infoarena5.png!
 - coloană de discuri ordonate descrescător de jos în sus
 
!{float:left;}problema/hanoi2?infoarena6.png!
  - coloană de discuri ordonate crescător de jos în sus
 
!{float:left;}problema/hanoi2?infoarena7.png!
- coloană de discuri neordonată
 
!{float:left;}problema/hanoi2?infoarena8.png!
   - tijă fără discuri

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="hanoi2") ==