Tarea 2 de Diseño de Algoritmos
Trimestre 2010 Primavera
Entrega: 21 de mayo de 2010 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 hanoiZZ (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.
Ejemplo de
entrada
|
Ejemplo de
salida
|
| 1 |
1 2
2 3
0 0
|
Problema 2: Sea N un entero
positivo y sea A1, A2, ..., AN un
vector de N enteros positivos distintos. Diremos que dos índices
I y J forman una inversión
si I < J pero AI > AJ. 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 A1 > A3, I = 2 y J = 3 porque A2
> A3 e I = 2 y J = 4 porque A2 > A4.
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 A1, A2, ..., AN (con 1 <= N
<= 1,000,000 y 1 <= AI <= 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.
| Ejemplo de
entrada |
Ejemplo de
salida |
5
2 4 1 3 5
|
3
|
Notas: Tus 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.