Tarea 4 de Diseño de Algoritmos
Trimestre 2007 Primavera
Entrega: 26 de junio de 2007 a las 22:00.
Problema 1: Sean A y B dos enteros
positivos con A < B. Considere la función recursiva definida
de la siguiente forma: F(N) = N para 0 <= N < B y F(N) = F(N-A) +
F(N-B) para N >= B. Diseñe un
algoritmo de programación dinámica que encuentre el valor
de F(N). Por ejemplo, si A = 1 y B = 2 entonces F(0) = 0, F(1) = 1,
F(2) = F(2-1) + F(2-2), etc. Escriba un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado seriesZZ (donde ZZ es una clave de dos
dígitos asignada por el profesor) basado en su algoritmo
que acepte como entrada tres números enteros A, B y N y que
escriba como salida el valor de F(N). De nuevo, si la entrada
fuera 1 2 5
entonces la salida debe ser 5.
Puede suponer que 0 < A < B <= 1,000 y que 0 <= N <=
1,000,000.
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 I1,
I2, ..., IS entonces M[I1] < M[I2]
< ... < M[IS] y L[I1] < L[I2]
< ... < L[IS]. 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 en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) 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. De
nuevo, si la entrada
fuera:
4
3 1 4 2
2 7 1 8
entonces la salida debe ser 2.
Puede suponer que todos los números involucrados son enteros del
1 al 10,000.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.