Tarea 3 de Análisis y Diseño de Algoritmos

Trimestre 2014 Invierno
Entrega: 27 de enero 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 australiaZZ (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 módulo M (es decir A[N] mod M). Por ejemplo si N = 5 y M = 3 entonces su programa debe calcular A[5] mod 3. 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. Por lo tanto A[5] mod 3 = 5 mod 3 = 2. Puede suponer que 0 <= N, M <= 100.

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.