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:
  1. A[1] = 1,
  2. A[3] = 3,
  3. A[2N] = A[N],
  4. A[4N+1] = 2 A[2N+1] - A[N] y
  5. 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.