Tarea 7 de Análisis y Diseño de Algoritmos
Trimestre 2016 Primavera
Entrega: 30 de junio de 2016 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 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: El problema ya
está en OmegaUp.
Pista: Si quieren usar memoización, observen que no pueden
pedir un arreglo de enteros de tamaño 1,000,000,000 pues eso
excede la memoria permitida (32MB). Pero como les expliqué en
clase, pueden usar otra estructura de datos.