Tarea 4 de Diseño de Algoritmos
Trimestre 2008 Primavera
Entrega: 28 de julio de 2008 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) = B-N para 0 <= N < B y F(N) = F(N-A)
+
F(N-B) para N >= B. Diseña 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) = 2, F(1) = 1,
F(2) = F(2-1) + F(2-2), etc.
Escribe un programa llamado lucasZZ
(donde ZZ es una clave de
dos
dígitos asignada por el profesor) basado en tu 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 11.
Puedes suponer que 0 < A < B <= 1,000 y que 0 <= N <=
1,000,000. Página de prueba.
Nota: Como F(N) puede llegar a
ser un número muy grande deberás escribir en la salida el
valor de F(N) módulo 1,000,000.
Ejemplo de
entrada
|
Ejemplo de
salida
|
1 2 5
|
11
|
Problema 2: La leyenda urbana
dice que si vas a la página de Google y buscas "Google" el
universo implotará. Por supuesto esto no es cierto, pero en un
universo paralelo sí es cierto que si vas a la página de
una máquina de búsqueda y buscas su nombre entonces ese
universo implotará. Para prevenir que esto pase, a la gente de
ese universo se le ocurrió la siguiente solución: Todas
las consultas a las máquinas de búsqueda se reúnen
en un sistema central que decide cuáles consultas van a
cuáles máquinas de búsqueda. El sistema central
envía una serie de consultas a una máquina de
búsqueda y puede cambiar de máquina de búsqueda en
cualquier instante. Las consultas deben procesarse en el orden en el
que hayan sido recibidas. El sistema central nunca debe enviar una
consulta a una máquina de búsqueda que coincida con su
nombre. Para reducir costos se debe minimizar la cantidad C de cambios
de máquina de búsqueda.
Como datos se tendrán la cantidad S de máquinas de
búsqueda (numeradas de la 1 a la S), la cantidad Q de consultas
(las que vamos a suponer que coinciden con los nombres de las
máquinas de búsqueda) y las Q consultas B1, B2,
..., BQ (que serán enteros del 1 al S). Por ejemplo,
si S = 5, Q = 10 y B = (1, 1, 5, 4, 5, 2, 4, 2, 3, 5) entonces se puede
resolver con C = 1 cambio, por ejemplo comenzando a enviar las primeras
8 consultas a la máquina de búsqueda número 3 y
las siguientes 2 consultas a la máquina de búsqueda
número 2.
Diseña un algoritmo de programación
dinámica que calcule C. Escribe un programa llamado salvaZZ (donde ZZ es una clave de
dos
dígitos asignada por el profesor) que implemente tu
algoritmo. Puedes suponer que 2 <= S <= 100 y 1 <= Q <=
1000. Página de prueba.
Nota: Este problema fué
adaptado de "Saving the Universe" del Google Summer of Code 2008.
| Ejemplo de
entrada |
Ejemplo de
salida |
5
10
1 1 5 4 5 2 4 2 3 5
|
1
|
Notas: Tus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado. El
tiempo de ejecución de tus algoritmos será considerado
como parte de la evaluación.