Problema 1: Los números de Padovan se definen de la siguiente manera: P(0) = 1, P(1) = 1, P(2) = 1 y P(N) = P(N-2) + P(N-3) para N >= 3. Escribe un programa llamado padoZZ (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 Padovan P(N) como la cantidad R de llamadas recursivas necesarias para obtener ese resultado. Por ejemplo si N = 5 entonces se llama a P(5), que a su vez llama a P(3) y a P(2). De estas dos, sólo P(3) hace llamadas recursivas a P(1) y a P(0), así en total se hacen R = 5 llamadas recursivas para calcular P(5) = 3. Puedes suponer que P(N) cabe en un entero de 64 bits sin signo.
| Ejemplos de entrada |
Ejemplos de salida |
| 5 |
3 5 |
| 6 |
4 7 |
Problema 2: Considere la definición recursiva de la función Z(n) dada por Z(1) = 1, Z(2) = 1 y para n >= 1 se tiene que Z(2n) = Z(n) * (Z(n+1) + Z(n)) y Z(2n+1) = Z(n)^2 + Z(n+1)^2. Escribe un programa llamado zetaZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea un entero N y que calcule tanto el valor de Z(N) como la cantidad R de llamadas recursivas necesarias para obtener ese resultado. Por ejemplo si N = 5 entonces se llama a Z(5), que a su vez llama a Z(2) y a Z(3). De estas dos, sólo Z(3) hace llamadas recursivas a Z(1) y a Z(2), así en total se hacen R = 5 llamadas recursivas para calcular Z(5) = 5. Puedes suponer que Z(N) cabe en un entero de 64 bits sin signo.
| Ejemplos de entrada |
Ejemplos de salida |
| 5 |
5 5 |
| 10 |
75 15 |
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.