Tarea 5 de Diseño de Algoritmos

Trimestre 2012 Invierno
Entrega: 9 de marzo de 2012 a las 22:00.

Observa que estos dos problemas son casi los mismos que uno de la tarea 1 y uno de la tarea 4, excepto que pueden involucrar valores de N mucho más grandes y cálculos módulo M. Para esto recuerda que las operaciones módulo M se pueden realizar indistintamente antes o después de otras operaciones, en particular (A+B) módulo M es igual a ((A módulo M) + (B módulo M)) módulo M y (A*B) módulo M es igual a ((A módulo M) * (B módulo M)) módulo M.

Problema 1: Sean N, P y Q tres enteros positivos. Diseña un algoritmo de memoización o de 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 sumameZZ (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

Problema 2: Los números de Sylvester se definen de la siguiente manera: S[0] = 2 y S[N] = S[N-1](S[N-1] - 1) + 1. Escribe un programa llamado sylvmeZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea dos enteros N, M y que calcule el N-ésimo número de Sylvester módulo M (es decir S[N] mod M). Por ejemplo si N = 3 y M = 5 entonces tu programa debe calcular S[3] mod 5 = 43 mod 5 = 3. Puedes suponer que 0 <= N, M <= 1,000,000.

Ejemplo de entrada
 Ejemplo de salida
3 5
 3

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.