Tarea 6 de Análisis y Diseño de Algoritmos
Trimestre 2014 Invierno
Entrega: 17 de febrero de 2014 a las 22:00.
La función recursiva australiana se define de la siguiente manera:
- A[1] = 1,
- A[3] = 3,
- A[2N] = A[N],
- A[4N+1] = 2 A[2N+1] - A[N] y
- A[4N+3] = 3 A[2N+1] - 2 A[N].
Escriba un programa llamado ailartsuaZZ
(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 australiano usando alguna forma de
memoización. Por ejemplo si N = 5 entonces su programa debe
calcular A[5]. Como 5 = 4*1+1 entonces se aplica la regla 4 para
obtener A[5] = 2 A[2*1+1] - A[1] = 2 A[3] - A[1] = 2*3 - 1 = 5.
Puede suponer que 1 <= N <= 1,000,000,000.
Ejemplo de entrada
|
Ejemplo de salida
|
5
|
5
|
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.