Tarea 2 de Diseño de Algoritmos
Trimestre 2012 Primavera
Entrega: 25 de mayo de 2012 a las 22:00.
Sea N un entero
positivo y considere el problema de las torres de Hanoi donde los
discos 1, 4, 7, ..., etc. son verdes, los discos 2, 5, 8, ..., etc. son
blancos, los discos 3, 6, 9, ..., etc. son rojos y no se permite poner
un disco sobre otro del mismo color. Diseñe un
algoritmo de divide y vencerás para mover los N discos de la
aguja 1 a la aguja 3. Observe que para N <= 3 la solución es
la misma que para el problema original de las torres de Hanoi. Escriba
un programa llamado thtresZZ
(donde ZZ es una clave de
dos dígitos asignada por el profesor) basado en su algoritmo que
acepte como entrada un entero N y que
escriba como salida una sucesión de movimientos para resolver el
problema (uno por renglón y terminando con 0 0). Puede suponer que 0
<= N <= 100.
Ejemplo de entrada
|
Ejemplo de salida
|
3
|
1
3
1 2
3 2
1 3
2 1
2 3
1 3
0 0 |
Notas: Sus programas no
deben
leer ni escribir nada adicional a lo que se indica en el
enunciado. El
tiempo de ejecución de sus algoritmos será considerado
como parte de la evaluación.