Ejercicios de inducción, recursión y memoización

Para todos los programas de abajo, la entrada será un entero no negativo n y la salida será el valor de Fn. Usa scanf y printf para la entrada y salida y el tipo unsigned long long int para todos tus variables y cálculos. No necesitas mandarme estos programas, simplemente convéncete de que funcionan. En cualquier caso, trata de descubrir el valor más grande de n para el cual tu programa termina (digamos, en menos de un segundo) con la respuesta correcta (¿qué podría fallar?).

  1. Escribe un programa (fibrec.c) que implemente el cálculo de los números de Fibonacci de forma recursiva.
  2. Escribe un programa (fibmem.c) que implemente el cálculo de los números de Fibonacci con memoización.
  3. Escribe un programa (fibtab.c) que implemente el cálculo de los números de Fibonacci con una tabla.
  4. Escribe un programa (fibcte.c) que implemente el cálculo de los números de Fibonacci con una cantidad constante de memoria.
  5. Demuestra por inducción en k que Fn = Fk+1 Fn-k + Fk Fn-k-1. Pista: Comienza con Fn = Fn-1 + Fn-2, sustituye Fn-1 = Fn-2 + Fn-3 y simplifica.
  6. Usando la fórmula anterior, demuestra que F2n = (Fn-1 + Fn+1) Fn y que F2n-1 = F2n + F2n-1. Pista: Escoge adecuadamente los valores de n y k.
  7. Usando las fórmulas anteriores, demuestra que se puede calcular F2n y F2n-1 usando sólamente Fn y Fn-1. Pista: Debes hacer una sustitución adicional.
  8. Escribe un programa (forrec.c) que implemente el cálculo recursivo de los números de Fibonacci usando estas fórmulas.
  9. Escribe un programa (formem.c) que implemente el cálculo memoizado de los números de Fibonacci usando estas fórmulas.