Problem
Puzzle “Torri di Hanoi” consiste di tre aste, numerate 1, 2, 3. Una piramide di n dischi di diverso diametro è posta sull'asta 1 in ordine crescente di diametro. I dischi possono essere trasferiti da un'asta all'altra uno alla volta, mentre il disco non può essere appoggiato su un disco di diametro inferiore. È necessario trasferire l'intera piramide dall'asta 1 all'asta 3 nel numero minimo di trasferimenti.
Scrivi un programma che risolva un enigma; per un dato numero di dischi n stampa una sequenza di permutazioni nel formato a b c, dove un — numero del disco spostato, b — il numero dell'asta da cui viene rimosso questo disco, c — il numero dell'asta su cui è posto questo disco.
Ad esempio, la riga 1 2 3 significa spostare il disco numero 1 dal pin 2 al pin 3. Un comando è stampato su una riga. I dischi sono numerati da 1 a n in ordine di diametro crescente.
Input
Inserisci un numero naturale n ( 0 < n < 11).
Uscita
Il programma dovrebbe visualizzare il modo minimo (in termini di numero di operazioni eseguite) di riordinare la piramide dal numero dato di dischi.
Esempi
| # |
Input |
Uscita |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until