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:

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

     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   5   9
(1) (2) (3) de la 2 la 3 \\
         5
         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
 
 

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