18/02/2020, 02:57:05 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Fibonacci hasta un n muy grande  (Leído 7492 veces)
0 Usuarios y 1 Visitante están viendo este tema.
leonardo09
Leonardo Andrés Jofré Flor
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 798

Leonardo Jofré


Ver Perfil WWW
« : 29/07/2008, 19:27:56 »

Usted es un experto en algoritmos recursivos, por lo cual piden que calcule la recursión de
Fibonacci, hasta el número [texx]n[/texx], 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 [texx]n [/texx] “grande” es por lo menos [texx]100[/texx]. La función de Fibonacci es:
[texx]F(0) = 1[/texx]
[texx]F(1) = 1[/texx]
[texx]F(n) = F(n-1)+F(n-2)[/texx]
En línea

nunca seré buen matemático
aesede
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 493



Ver Perfil
« Respuesta #1 : 29/07/2008, 19:52:23 »

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:

[texx]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[/texx]

Spoiler (click para mostrar u ocultar)

Espero que sea lo que buscabas, saludos :sonrisa:
En línea
leonardo09
Leonardo Andrés Jofré Flor
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 798

Leonardo Jofré


Ver Perfil WWW
« Respuesta #2 : 29/07/2008, 20:24:32 »

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
En línea

nunca seré buen matemático
aesede
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 493



Ver Perfil
« Respuesta #3 : 29/07/2008, 20:35:12 »

Ahh. Perdoná :lengua_afuera:

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:
#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:
/***************************************************************************
 * 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.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.967


Ver Perfil
« Respuesta #4 : 30/07/2008, 04:10:06 »

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 [texx]-1[/texx] (hasta el tope máximo de [texx]n[/texx] 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.
En línea
leonardo09
Leonardo Andrés Jofré Flor
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 798

Leonardo Jofré


Ver Perfil WWW
« Respuesta #5 : 30/07/2008, 18:52:06 »

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
En línea

nunca seré buen matemático
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.967


Ver Perfil
« Respuesta #6 : 31/07/2008, 05:03:18 »

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:

[texx]-2^{31}+1=-2147483647[/texx] a [texx]2^{31}=2147483648[/texx]

 A partir de [texx]n=48[/texx], 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.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!