[leonardo09]

Usted es un experto en algoritmos recursivos, por lo cual piden que calcule la recursión de
Fibonacci, hasta el número \( n \), pero como es sabido, calcular Fibonacci hasta un n muy grande
tarda mucho tiempo, le solicitan que mejore el algoritmo para que tarde el menor tiempo posible,
pero sin perder la recursividad.
Consideraciones
El usuario es inteligente y el número \( n  \) “grande” es por lo menos \( 100 \). La función de Fibonacci es:
\( F(0) = 1 \)
\( F(1) = 1 \)
\( F(n) = F(n-1)+F(n-2) \)

[aesede]

Si resolvemos la relación de recurrencia de Fibonacci, podemos encontrar una ecuación que nos permita calcular el término n-ésimo. La fórmula que te permite obtener un término cualquiera de la sucesión (tan grande como quieras) es:

\( a_n = \displaystyle\frac{1}{\sqrt[ ]{5}} ( \displaystyle\frac{1+\sqrt[ ]{5}}{2} )^n - \displaystyle\frac{1}{\sqrt[ ]{5}} ( \displaystyle\frac{1-\sqrt[ ]{5}}{2} )^n \)

Spoiler

La sucesión de Fibonacci es una relación de recurrencia lineal, de segundo orden, homogénea, con coeficientes constantes.

Las condiciones iniciales son \( a_0 = 0 \) y \( a_1 = 1 \)

Puesta en la forma \( a_n - a_{n-1} - a_{n-2} = 0 \) la ecuación característica que permite resolverla es \( \lambda ^2 - \lambda- 1 = 0 \), cuyas raíces (reales y distintas) son:

\( \lambda _ 1 = \displaystyle\frac{1+\sqrt[ ]{5}}{2} \) y \( \lambda _ 2 = \displaystyle\frac{1-\sqrt[ ]{5}}{2} \)

La solución explícita general viene dada por \( a_n = A_1 ( \displaystyle\frac{1+\sqrt[ ]{5}}{2} )^n + A_2 ( \displaystyle\frac{1-\sqrt[ ]{5}}{2} )^n \)

donde:

\( a_0 = 0 = A_1 + A_2 \)

y

\( a_1 = 1 = A_1 \displaystyle\frac{1+\sqrt[ ]{5}}{2} + A_2 \displaystyle\frac{1-\sqrt[ ]{5}}{2} \)

Obtenemos \( A_1 = \displaystyle\frac{1}{\sqrt[ ]{5}} \) y \( A_2 = - \displaystyle\frac{1}{\sqrt[ ]{5}} \)

Luego,

\( a_n = \displaystyle\frac{1}{\sqrt[ ]{5}} ( \displaystyle\frac{1+\sqrt[ ]{5}}{2} )^n - \displaystyle\frac{1}{\sqrt[ ]{5}} ( \displaystyle\frac{1-\sqrt[ ]{5}}{2} )^n \)

[cerrar]

Espero que sea lo que buscabas, saludos

[leonardo09]

Gracias por tu respuesta, lo que pasa es que tengo que hacer el programa en lenguaje C y debe ser recursiva, si te fijas bien, si uso esa funcion explicita en C , el punto flotante no me va a dar exacto por el numero de oro que es irracional, finalmente es imperativo que sea recursiva pero rapida

[aesede]

Ahh. Perdoná

Te dejo un algoritmo (en C). Es rápido, te va guardando los dos ultimos numeros que calculaste. No almacena los demás números, es decir, los muestra pero no los guarda en ningún lado. Podrías crear un array y, a la vez que muestra un término, guardarlo.

Código: [Seleccionar]

#include<stdio.h>
#include<conio.h>

void main() {
   clrscr();
   //n es la cantidad de terminos a mostrar
   int primero=0,segundo=1,n=15,i,ultimo;
   printf("%d - ",primero);
   for(i=1;i<=n-1;i++) {
      ultimo = primero + segundo;
      primero = segundo;
      segundo = ultimo;
      printf("%d - ",ultimo);
   }
   getch();
}
Este otro te calcula el término n-ésimo de la sucesión:

Código: [Seleccionar]

/***************************************************************************
 * Calculo recursivo del n-esimo termino de fibonacci
 * Por definicion:
 *    Fibonacci(0) = 0
 *    Fibonacci(1) = 1
 *    Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)
 ***************************************************************************/


/***************************************************************************
 * Funcion recursiva que calcula el n-esimo termino de fibonacci
 ***************************************************************************/

double Fibonacci(int n) {
   switch (n) {
     case 0 : return 0;
     case 1 : return 1;
     default: return Fibonacci(n - 1) + Fibonacci(n - 2);
                   /* ^-- Llamado recursivo --^ */
   }
}

/***************************************************************************
 * Programa que calcula, de forma recursiva, el termino n-esimo de la
 * sucesion de fibonacci, para un valor n dado por el usuario.
 ***************************************************************************/

main() {
   int n;

   /* Se solicita al usuario el valor de n */
   printf("Ingrese el valor de n: ");
   scanf("%d", &n);   /* scanf requiere puntero: & */

   /* Imprime el fibonacci de n */
   printf("El termino %d de Fibonacci es: %.0lf\n", n, Fibonacci(n));
}

Fuente: http://www2.ing.puc.cl/~iic11021/materia/EjsC/fiborec.c

Saludos.

[Luis Fuentes]

Hola

 Puedes usar algo así:

double Fibonacci2(double *lista, int n) {
       if (lista[n]<=-1)  lista[n]=Fibonacci2(lista,n-1)+Fibonacci2(lista,n-2);
       return lista[n];     
}

 Previamente debes inicializar el vector lista cont todos sus valores a \( -1 \) (hasta el tope máximo de \( n \) que permitas) y almacenar en lista[0] y lista[1] los dos primeros valores de la sucesión.

 Lo que hace este agloritmo es no recalcular los números que ya había hallado previamente. Los mantiene almacenados en lista y los utiliza cuando los necesita.

Saludos.

[leonardo09]

acabo de hacer el programa con un algoritmo muy rapido pero existe un error no fatal que es dificilmente identificable

aqui va:

#include <stdio.h>

 int FIB_AUX(int, int, int );

main()
{
 int n, p = 0;
 
 printf("ingrese la cantidad de terminos de la serie y disfrute la velocidad:");
 scanf("%d", &n);
 while(p <= n){
         
         printf("El %d-numero de la serie Fibonacci es:%d\n", p, FIB_AUX(p, 1, 0));
         p++;
}
 getchar();
 getchar();
 return (0);
 
}

/*En el caso de Fibonacci esa ineficacia es fácilmente superable:  Precisamente
se define una función auxiliar que tiene una acumulación de argumentos para
retener los valores previamente calculados.  La función principal invoca a esa
función auxiliar con los argumentos iniciales apropiados.*/

 int FIB_AUX(int n, int f1, int f0)
{
 if(n == 0)
 return (f0);
else
 return FIB_AUX(n - 1, f1 + f0, f1);         
}
/*Se supone que debería funcionar para cualquier valor entero positivo
incluyendo el cero ya que se pasó de una
doble recursivadad que hacia una cantidad exponencial de invocaciones a una de
una sola recursividad cuyas invocaciones es directamente proporcional al termino
que se pide, pero en el término n = 48 existe un "error no fatal" dificil de
identificar,¡intentalo!, si me puedes decir el error no fatal me harias un gran
favor

Finalmente queda a tu criterio, pero insisto ¡intentalo!*/

¿Dónde está el error ?
este algoritmo es el usado por derive asi que no entiendo donde falla

[Luis Fuentes]

Hola

 Simplemente es un problema de tipos de datos.

 El tipo int (que parece que por omisión lo toma como un long int) sólo puede almacenar números desde:

\( -2^{31}+1=-2147483647 \) a \( 2^{31}=2147483648 \)

 A partir de \( n=48 \), los números de Fibonacci superan esa cota superior. Así que si quieres que siga calculando debes de calcular el tipo de dato a double, por ejemplo.

Saludos.