Torri di Hanoi
Sono presenti 3 aste (sinistra - 1, centrale - 2 e destra - 3), con
n dischi rotondi di diverse dimensioni sulla prima asta. I dischi sono disposti in ordine crescente di grandezza dal più piccolo in cima al più grande in fondo. È consentito spostare soltanto il disco superiore da un’asta a un’altra e collocarlo sopra un disco più grande. Non è quindi consentito posizionare un disco più grande su uno più piccolo.Si richiede di stampare tutte le operazioni necessarie per spostare tutti i dischi dalla prima asta alla terza, assicurandosi che il numero di mosse sia minimo.
Input
L’input contiene un singolo intero
n (1 ≤ n ≤ 16), che rappresenta il numero di dischi sulla prima asta.Output
Il programma deve stampare tutte le operazioni richieste per spostare i dischi dalla prima asta alla terza, garantendo che su ogni asta i dischi siano sempre in ordine di grandezza (dal più piccolo in alto al più grande in basso). Il numero di operazioni non deve superare .
Esempi
Input | Output |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB