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

Trimestre 2015 Invierno
Entrega: 1 de febrero de 2015 a las 22:00 (los tres programas).
Entrega: 30 de enero de 2015 en clase (las dos preguntas).

1. Escribe programas llamados edadNN.c, burroNN.c y caballoNN.c (donde NN es tu número de lista) que resuelvan los tres problemas de la etapa calificatoria del XII Concurso de Programación de la UAM. Debes usar el sitio OmegaUp para probar tus programas. POR UNICA OCASION debes enviar esta tarea desde tu correo personal al correo uam15acm@gmail.com para que se considere en tu calificación del curso
2. Demuestra que el siguiente algoritmo iterativo para dividir números enteros es correcto. Los invariantes son q_jw_j + r_j = y₀ y r_j < w_j.
   divide(y, z)
     r := y
     q := 0
     w := z
     mientras w <= y
       w := 2w
     mientras w > z
       q := 2q
       w := w/2 /* parte entera */
       si w <= r entonces
         r := r - w
         q := q + 1
     regresa (q,r) /* y = qz+r con r<z */
   
3. Demuestra que el siguiente algoritmo recursivo calcula 3ⁿ - 2ⁿ para toda n.
   calcula(n)
     si n <= 1 entonces
       regresa n
     si no
       regresa 5 calcula(n-1) - 6 calcula(n-2)