elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse)
| | |-+  Problema para compuilar Fibonacci
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Problema para compuilar Fibonacci  (Leído 2,251 veces)
YePs

Desconectado Desconectado

Mensajes: 7



Ver Perfil
Re: Problema para compuilar Fibonacci
« Respuesta #10 en: 22 Febrero 2009, 16:12 »

Pues las especificaciones de las funciones serian así:
Version recursiva:

funcion Fibonacci(n:entero) retorna (e:entero)
si n=1 o n=2 entonces retorna 1
si no retorna Diecinueve (n-1) + Diecinueve (n-2)
fsi
ffuncion

este algoritmo da lugar a una complejidad T(n) ∈ Ω(2n/2) y T(n) ∈ O(2n) (ENORME) es un coste tan elevado que es imposible de asumir para n grandes

Version iterativa:

función Fibonacci(n:entero) retorna (e:entero)
a=1
b=1
para i=1 hasta n-2
b=a+b
a=b-a
fpara
retorna b
ffunción

con un coste temporal T(n) ∈ θ(n) (ridiculo en comparacion con el recursivo)


en cuanto consiga acceder al servidor de la universidad intentare colgar el codigo fuente de ambas versiones.


« Última modificación: 22 Febrero 2009, 16:17 por YePs » En línea

Pc:
DELL inspiron 1520 "PixelVortex"
2Gb RAM
Intel Core2Duo 2.0
HDD WesternDigital 250Gb
Nvidia Geforce 8600mGT 256Mb
Windows Vista Home Premium/Ubuntu 7.10
chrominum


Desconectado Desconectado

Mensajes: 564


Viceroy: No es lo que tengo, es COMO lo tengo


Ver Perfil WWW
Re: Problema para compuilar Fibonacci
« Respuesta #11 en: 22 Febrero 2009, 17:53 »

Pues las especificaciones de las funciones serian así:
Version recursiva:

funcion Fibonacci(n:entero) retorna (e:entero)
si n=1 o n=2 entonces retorna 1
si no retorna Diecinueve (n-1) + Diecinueve (n-2)
fsi
ffuncion

este algoritmo da lugar a una complejidad T(n) ∈ Ω(2n/2) y T(n) ∈ O(2n) (ENORME) es un coste tan elevado que es imposible de asumir para n grandes

Version iterativa:

función Fibonacci(n:entero) retorna (e:entero)
a=1
b=1
para i=1 hasta n-2
b=a+b
a=b-a
fpara
retorna b
ffunción

con un coste temporal T(n) ∈ θ(n) (ridiculo en comparacion con el recursivo)


en cuanto consiga acceder al servidor de la universidad intentare colgar el codigo fuente de ambas versiones.

Que no, que no te estas enterando  :xD Todo lo que has dicho ya lo se  :xD Yo decia que el mejor algortimo era el 3 (Versión divide y vencerás) con complejidad log(n) pero que no lo habia traducido a C porque no lo entendia (unicamente ese, si los otros 2 ya habia posteado el codigo yo).


« Última modificación: 22 Febrero 2009, 17:55 por Chungakotorodunga Chunga Chunga » En línea

YePs

Desconectado Desconectado

Mensajes: 7



Ver Perfil
Re: Problema para compuilar Fibonacci
« Respuesta #12 en: 22 Febrero 2009, 19:06 »

Vale, no te habia entendido  ;)

he intentado transladar el codigo de la wikipedia a C y me ha quedado asi:
Código
  1. int fibonacci(const int n){
  2.    if(n<=0) return 0;
  3.    int i=n-1;
  4.    int a,b,c,d,a2,c2;
  5.    a=1;
  6.    d=1;
  7.    b=0;
  8.    c=0;
  9.  
  10. //(a,b)=(1,0); (c,d)=(0,1)
  11.  
  12.    while(i>0){
  13.               if(i%2==1){
  14.                          a2=a;
  15.                          a=((d*b)+(c*a));
  16.                          b=((d*(b+a2))+(c*b));
  17.                          }
  18.               c2=c;
  19.               c=((c*c)+(d*d));
  20.               d=d*((2*c2)+d);
  21.               i=i/2;
  22.               }
  23.    return a+b;
  24. }
  25.  

PD: a2 y c2 los he declarado porque en el esquema formal de la wiki asigna los valores por pares simultaneamente, pero en el codigo si se modifica a y luego b, esta segunda modificacion ha de hacerse con el valor que tenia a despues del if.

espero que sea de ayuda  ;D
En línea

Pc:
DELL inspiron 1520 "PixelVortex"
2Gb RAM
Intel Core2Duo 2.0
HDD WesternDigital 250Gb
Nvidia Geforce 8600mGT 256Mb
Windows Vista Home Premium/Ubuntu 7.10
Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
FIBONACCI « 1 2 »
Programación C/C++
JOSE23 12 10,417 Último mensaje 24 Febrero 2011, 00:09
por RyogiShiki
¿Un acumulador para sumar la serie fibonacci?
Programación C/C++
Exorcista12 2 1,399 Último mensaje 17 Enero 2014, 06:48
por Exorcista12
Por favor una pista para criptografia fibonacci.
Dudas Generales
BigKhalPablo 1 989 Último mensaje 27 Noviembre 2016, 21:17
por engel lex
Problema con programa Fibonacci que trabaja con tablas
Programación C/C++
Enri_f99 2 553 Último mensaje 3 Diciembre 2017, 05:54
por BloodSharp
Problema con programa Fibonacci que trabaja con tablas
Programación C/C++
Enri_f99 1 318 Último mensaje 8 Diciembre 2017, 00:22
por BloodSharp
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines