Observa que estos dos problemas son casi los mismos de la Tarea 1,
excepto que involucran 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: 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
usando memorización o programación dinámica
llamado padopdZZ (donde ZZ es la clave de
dos
dígitos asignada por el profesor) que lea dos enteros N y M y
que
calcule el N-ésimo número de Padovan P(N). Como este
número puede ser muy grande, el resultado lo deberás
expresar módulo M. Por ejemplo si N = 10 y M = 5 entonces P(10)
= 12 y esto módulo 5 es igual a 2. Puedes suponer que 0 <= N
<= 1,000,000 y que 2 <= M <= 1000.
| Ejemplo de entrada |
Ejemplo de salida |
| 10 5 |
2 |
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 usando memorización o programación dinámica llamado zetapdZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea dos enteros N y M y que calcule el valor de Z(N). Como este número puede ser muy grande, el resultado lo deberás expresar módulo M. Por ejemplo si N = 10 y M = 7 entonces Z(10) = 75 y esto módulo 7 es igual a 5. Puedes suponer que 0 <= N <= 1,000,000 y que 2 <= M <= 1000.
| Ejemplo de entrada |
Ejemplo de salida |
| 10 7 |
5 |
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.