Tarea 2 de Diseño de Algoritmos

Trimestre 2012 Invierno
Entrega: 10 de febrero de 2012 a las 22:00.

Problema 1: Diseña 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. Escribe un programa llamado hanoimZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada un entero positivo N (con 1 <= N <= 20) 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.

Problema 2: Sea N un entero positivo y sea A₁, A₂, ..., A_N un vector de N enteros positivos distintos. Diremos que dos índices I y J forman una inversión si I < J pero A_I > A_J. Diseña un algoritmo de divide y vencerás que calcule la cantidad de inversiones en el vector A. Por ejemplo, si N = 5 y A = (2, 4, 1, 3, 5) entonces se tienen tres inversiones: I = 1 y J = 3 porque A₁ > A₃, I = 2 y J = 3 porque A₂ > A₃ e I = 2 y J = 4 porque A₂ > A₄. Escribe un programa llamado inversZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa será un entero N seguido de los N enteros A₁, A₂, ..., A_N (con 1 <= N <= 1,000,000 y 1 <= A_I <= 1,000,000,000) y la salida de tu programa será un entero R (la cantidad de inversiones). Idea: Trata de modificar el algoritmo de ordenamiento por mezcla. En particular observa que si has dividido la lista en dos mitades ordenadas, entonces el número total de inversiones son las que había en cada mitad mas las que se forman con un elemento de cada una de las mitades.

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.