UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Entrega: 9 de febrero de 2006 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 no se permite mover ningún disco entre las agujas 1 y 3, es decir, todos los movimientos deben ser desde o hacia la aguja 2. 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?