Tarea 6 de Diseño de Algoritmos
Trimestre 2013 Otoño
Entrega: 9 de octubre de 2013 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 recursivo 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 lucasrZZ
(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 <=
100. 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: Diseña un
algoritmo con memoización que encuentre el valor
de F(N) del problema anterior. Escribe un programa llamado lucasmZZ
(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. 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
|
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.