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.