Tarea 6 de Diseño de Algoritmos

Trimestre 2012 Invierno
Entrega: 19 de marzo de 2012 a las 22:00.

Problema 1: Diseña un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Sea N un entero positivo y sean A y B dos arreglos A[1], A[2], ..., A[N] y B[1], B[2], ..., B[N] de enteros positivos. Los índices 1 <= I₁ < I₂ < ... < I_K <= N y 1 <= J₁ < J₂ < ... < J_K <= N forman un subarreglo ascendente común de A y B de longitud K si se cumple que A[I₁] = B[J₁] < A[I₂] = B[J₂] < ... < A[I_K] = B[J_K]. Su algoritmo deberá encontrar un subarreglo ascendente común de A y B con la mayor longitud posible. Por ejemplo, si N = 9, A = [3, 1, 4, 1, 5, 9, 2, 6, 5] y B = [9, 2, 1, 3, 4, 6, 5, 7, 6] entonces los índices I₁ = 1, I₂ = 3, I₃ = 5 e I₄ = 8 y J₁ = 4, J₂ = 5, J₃ = 7 e I₄ = 9 forman el subarreglo ascendente [3, 4, 5, 6] de longitud 4. Escribe un programa llamado sascomZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada el entero positivo N y dos arreglos A y B de N enteros positivos y que escriba como salida la máxima longitud K de un subarreglo ascendente común de A y B. Puedes suponer que 1 <= N <= 1000 y que A y B son arreglos de int.

Problema 2: Algunas personas piensan que los perros que ladran mucho muerden poco. Para demostrar lo contrario se quiere analizar una colección de perros y escoger tantos de ellos en una secuencia en la que tanto el número de ladridos como el número de mordidas vayan en orden creciente. Sea P un entero positivo que denota al número de perros en la colección, L[1], L[2], ..., L[P] un vector de enteros positivos indicando el número de ladridos de cada uno de los P perros y M[1], M[2], ..., M[P] el número de mordidas de cada uno de los P perros. Diseñe un algoritmo de programación dinámica que encuentre la máxima longitud S de la secuencia con las propiedades pedidas. En otras palabras, si los L perros escogidos son los perros I₁, I₂, ..., I_S entonces M[I₁] < M[I₂] < ... < M[I_S] y L[I₁] < L[I₂] < ... < L[I_S]. Por ejemplo, si P = 4, L = (3, 1, 4, 2) y M = (2, 7, 1, 8) entonces S = 2 ya que se puede escoger a los perros 2 y 4 con M[2] < M[4] y L[2] < L[4]. Escriba un programa llamado muerdeZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) basado en su algoritmo que acepte como entrada un número entero P, seguido de un renglón con P números enteros L[1], L[2], ..., L[P] separados por espacios y seguido de un renglón con otros P números enteros M[1], M[2], ..., M[P] y que escriba como salida la máxima longitud S de la secuencia con las propiedades pedidas. Puede suponer que todos los números involucrados son enteros del 1 al 10,000.