UEA: Diseño de Algoritmos
Trimestre: 2007 Invierno
Entrega: 2 de febrero de 2007 a las 10pm

Diseñe un algoritmo usando la técnica de divide y vencerás para resolver el problema de las torres de Hanoi con la restricción adicional de que sólo se permiten mover discos de la aguja 1 a la 2, de la aguja 2 a la 3 y de la aguja 3 a la 1. Escriba un programa basado en su algoritmo que acepte como entrada un entero positivo N y que escriba como salida una lista de movimientos que muevan los N discos de la aguja 1 a la aguja 3. La lista debe contener dos enteros en cada renglón: 0 0 para indicar que terminó, mientras que A B significa que se movió un disco de la aguja A a la aguja B. Por ejemplo, si N = 1 una posible salida contiene los tres renglones 1 2, 2 3 y 0 0. Diga cuántos movimientos necesita su programa para resolver el problema para toda N menor que 5. ¿Está seguro de que eso es lo mejor posible? ¿Cuál es el valor de N más grande que puede resolver en un minuto? ¿Y en una hora?