Fişierul intrare/ieşire: | hanoi.in, hanoi.out | Sursă | Cerc informatică Vianu |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 1 sec | Limită de memorie | 2048 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Hanoi (clasele 7-8)
Turnurile din hanoi. Fie trei tije, 1 2 şi 3 şi n discuri perforate de diametre diferite. Discurile sînt aşezate iniţial pe tija 1 în ordinea descrescătoare a diametrelor acestora, considerînd sensul de la bază la vîrf. Problema constă în a muta turnul de n discuri de pe tija 1 pe tija 2 ţinînd cont de următoarele reguli:
- La fiecare mutare se mută un singur disc, care se află în vîrful unui turn
- În permanenţă, pe fiecare tijă, deasupra unui disc pot fi mutate numai discuri de diametre mai mici.
Discurile sînt numerotate de la 1 la n în ordinea mărimii lor (1 este discul cel mai mic).
Cerinţă
Dat numărul de discuri n să se afişeze o suită de mutări care rezolvă problema turnurilor din hanoi.
Date de intrare
Fişierul de intrare hanoi.in conţine un singur număr şi anume numărul de discuri n.
Date de ieşire
În fişierul de ieşire hanoi.out se vor scrie mai multe mutări, cîte o mutare pe linie. O linie va fi de forma:
<număr disc> <tijă sursă> <tijă destinaţie>
Se cere ca în urma efectuării tuturor mutărilor din fişierul de ieşire grămada de discuri să se afle la final pe tija 2.
Restricţii
- 1 ≤ n ≤ 20
- Orice secvenţă de corectă de mutări este acceptată
Exemplu
hanoi.in | hanoi.out | Explicaţie |
---|---|---|
3 | 1 1 2 2 1 3 1 2 3 3 1 2 1 3 1 2 3 2 1 1 2 | Mutăm discul 1 de pe tija 1 pe tija 2 Mutăm discul 2 de pe tija 1 pe tija 3 Mutăm discul 1 de pe tija 2 pe tija 3 Mutăm discul 3 de pe tija 1 pe tija 2 Mutăm discul 1 de pe tija 3 pe tija 1 Mutăm discul 2 de pe tija 3 pe tija 2 Mutăm discul 1 de pe tija 1 pe tija 2 |