Tarea 2 de Diseño de Algoritmos

Trimestre 2008 Primavera
Entrega: 14 de julio de 2008 a las 22:00.

Problema 1: Sea N un entero positivo y sea A1, A2, ..., AN un vector de N enteros positivos distintos. Escribe un programa llamado pseudoZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que lleve a cabo el siguiente algoritmo de divide y vencerás: si el vector sólo tiene un elemento entonces regresa ese elemento, si el vector tiene dos elementos entonces regresa el mayor de esos dos, si el vector tiene tres elementos entonces regresa el de enmedio (es decir, el que no es ni el mayor ni el menor) y si el vector tiene N > 3 elementos entonces aplícale recursivamente este algoritmo al vector obtenido al aplicarle esta regla a las listas (A1, A2, A3), (A4, A5, A6), ..., es decir tomando los elementos del vector de tres en tres (excepto que el último grupo tal vez sólo tiene dos o un elementos). Por ejemplo, si N = 10 y A = (42, 85, 63, 47, 65, 58, 34, 86, 53, 91) entonces las primeras listas son (42, 85, 63), (47, 65, 58), (34, 86, 53) y (91) de donde se obtiene el nuevo vector (63, 58, 53, 91) y las segundas listas (63, 58, 53) y (91) de donde se obtiene el nuevo vector (58, 91) el cual ya es un caso base y se regresa 91. 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 P (el valor regresado por el algoritmo) seguido de otro entero C (el número de comparaciones realizadas por el algoritmo). Página de prueba.

Ejemplo de entrada
Ejemplo de salida
10
42 85 63 47 65 58 34 86 53 91
91 13

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. Página de prueba.

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.