Tarea 6 de Diseño de Algoritmos
Trimestre 2012 Primavera
Entrega: 22 de junio de 2012 a las 22:00.
Los
números de Jacobsthal se definen de la siguiente manera: J[0] =
0, J[1] = 1
y J[N] = J[N-1] + 2J[N-2] para N > 1. Usando la técnica de memoización, escriba un
programa llamado mjacobZZ
(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 Jacobsthal módulo M
(es decir J[N] mod M). Por ejemplo si N = 5 y M = 3 entonces su
programa debe calcular J[5] mod 3 = 11 mod 3 = 2. Puede suponer que 0
<= N <= 1,000,000 y 1 <= M <= 1,000,000.
Ejemplo de entrada
|
Ejemplo de salida
|
5 3
|
2
|
Notas: Sus 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.