Tarea 5 de Diseño de Algoritmos

Trimestre 2010 Primavera
Entrega: 23 de junio de 2010 a las 22:00.

Por favor noten que son casi los mismos problemas que los de la Tarea 1 y de la Tarea 4, posiblemente con nuevas restricciones:

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 basado en un  algoritmo de memorización o programación dinámica y llamado pdpellZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea un entero N y que calcule el N-ésimo número de Pell P(N). Por ejemplo si N = 3 entonces P(3) = 5. Puedes suponer que 0 <= N <= 1,000,000. Todos los cálculos los debes hacer con enteros de 64 bits con signo.

Ejemplo de entrada
 Ejemplo de salida
3
 5

Problema 2: Sean N, P y Q tres enteros positivos. Diseña un algoritmo de memorización o programación dinámica que calcule la cantidad S de formas en que se puede obtener el valor N sumando enteros distintos entre P y Q. Dos sumas se consideran idénticas si sólo difieren en el orden de sus sumandos. Por ejemplo, si N = 12, P = 3 y Q = 7 entonces S = 2 porque 12 se puede obtener de las siguientes formas: 3+4+5 y 5+7. Escribe un programa llamado pdsumaZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa serán los tres enteros N, P y Q (con 1 <= P <= Q <= N <= 1000) y la salida de tu programa será el entero S.

Ejemplo de entrada Ejemplo de salida
12 3 7
 2

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.