Tarea 3 de Algoritmos y Estructuras de Datos
Trimestre 2014 Primavera
Entrega: 16 de mayo de 2014 a las 22:00
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.c
(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 sin signo.
Entrada 1
|
Salida 1
|
Entrada 2
|
Salida 2
|
3
|
5 5
|
2
|
2 3
|
Nota: Tu programa no debe imprimir letreros adicionales ni
tampoco debe pausarse antes de terminar su ejecución.