Problema 1: Los
números de Pell se definen de la siguiente manera: P(0) = 0,
P(1) = 1 y P(N) = 2 P(N-1) + P(N-2) para N > 1. Escribe un programa
llamado pellZZ (donde ZZ es la clave de
dos
dígitos asignada por el profesor) que lea un entero N y que
calcule tanto el N-ésimo número de Pell P(N) como la
cantidad R de llamadas recursivas necesarias para obtener ese
resultado. Por ejemplo si N = 3 entonces se llama a P(3), que a su vez
llama a P(2) y a P(1). De estas dos, sólo P(2) hace llamadas
recursivas a P(1) y a P(0), así en total se hacen R = 5 llamadas
recursivas para calcular P(3) = 5. Puedes suponer que P(N) cabe en un
entero de 64 bits con signo.
| Ejemplos de entrada |
Ejemplos de salida |
| 3 |
5 5 |
| 2 |
2 3 |
Problema 2: Los números de Perrin se definen de la siguiente manera: P(0) = 3, P(1) = 0, P(2) = 2 y P(N) = P(N-1) + P(N-3) para N > 2. Escribe un programa llamado perrinZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea un entero N y que calcule tanto el N-ésimo número de Perrin P(N) como la cantidad R de llamadas recursivas necesarias para obtener ese resultado. Por ejemplo si N = 3 entonces se llama a P(3), que a su vez llama a P(2) y a P(0). Ninguna de estas dos hace llamadas recursivas, así en total se hacen R = 3 llamadas recursivas para calcular P(3) = 5. Puedes suponer que P(N) cabe en un entero de 64 bits con signo.
| Ejemplos de entrada |
Ejemplos de salida |
| 3 |
5 3 |
| 2 |
2 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 sus algoritmos será considerado como parte de la evaluación.