Dev - C++ - C++ Relación con la Sucesion Fibonacci

   
Vista:

C++ Relación con la Sucesion Fibonacci

Publicado por Juan (1 intervención) el 11/06/2012 01:02:55
Hola,
Me encontraba leyendo sobre la recursión en las funciones y pues me puse a practicar, ya que me encuentro aprendiendo C++ utilizo el dev-cpp, en fin me puse a practicar y logre hacer mi programa con mi concepto básico de lo que era la sucesión fibonacci, en fin... El hecho es que al seguir leyendo me encuentro con la sucesión pero esta terminaba con:

return ( fib(n-1)+fib(n-2) )

Mientras que a mi me habia quedado asi:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
 
using namespace std;
void fibonacci(int);
int previo=0,ultimo=1,sucesion;
int main()
{
int cantidad;
cout << "Ingrese una cantidad: "; cin>>cantidad;
cout << endl;
if (cantidad>0)
{
cout << "Sucesion: 1,"; cantidad--;
fibonacci(cantidad);
}
else
{
cout << "Numero Invalido!" << endl;
}
cout << endl; cout << endl;
system("PAUSE");
return 0;
}
 
void fibonacci(int cantidad)
{
            if(cantidad>0)
            {
            sucesion=previo+ultimo;
            cout << sucesion << ","; previo=ultimo; ultimo=sucesion;
            cantidad--;
            fibonacci(cantidad);
            }
}


Para no hacer larga la historia, quede perdido por un instante ya que logicamente para encontrar la posición 5 por ejemplo (5-1)+(5-2)=7 mientras que no me daba ese resultado... luego de un rato segui buscando y encontre, que era la formula para saber el valor de esa posicion y segun el texto que encontre la sucesion empieza con [0,1].

Por tanto (5-1)=4. La posición 4 tiene el valor "2". Entonces (5-2)=3. La posición 3 es "1". Es decir que el ejemplo anterior (5-1)+(5-2)=3.

[0,1,1,2,3,5,8] Si se fijan la posición quinta es el 3 entonces estaría correcto. Bueno ya di muchas vueltas pero mi duda finalmente es, porque C++ entiende esto? Me podria dar problemas o como puedo evitarlo, ya que no es muy logico si se trata de otra operación.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

C Relación con la Sucesion Fibonacci

Publicado por Capitan Kirk capitan.kirk09@gmail.com (44 intervenciones) el 11/06/2012 12:53:04
La sucesión de Fibonacci consiste en que cada término de la sucesión es la suma de los dos anteriores. La sucesión se define:

Fib(0) = 0
Fib(1) = 1

y a partir de aquí:

Fib(n) = Fib(n-1) + Fib(n-2)

es decir, se trata de una función recursiva (se llama a sí misma).

En tal caso,

Fib(5) = Fib(5-1) + Fib(5-2) = Fib(4) + Fib(3) = 3+2 = 5

Ten en cuenta que el primer elemento corresponde a Fib(0), que vale 0, no a Fib(1).

Dado que es una función recursiva, hay que tener muy clara la condición de retorno (si la implementas de manera recursiva). Por ejemplo:
1
2
3
4
5
6
7
int Fibonacci (int cantidad)
{
	if (cantidad == 0)	return 0;
	if (cantidad == 1)	return 1;
 
	return ( Fibonacci(cantidad-1) + Fibonacci(cantidad-2) );
}

Si utilizas esta función recursiva a partir de la definición, verás que el tiempo de ejecución empieza a ser notorio con cantidades no muy elevadas (a partir de 35-40). Este problema se da con frecuencia en el empleo de funciones recursivas.

En cambio, con la versión no recursiva, por ejemplo,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Fibonacci (int cantidad)
{
	int total=0, previo=0, ultimo=1;
 
	if (cantidad == 0)	return 0;
	if (cantidad == 1)	return 1;
	while (--cantidad > 0)
	{
		total = previo + ultimo;
		previo = ultimo;
		ultimo = total;
	}
	return total;
}

la respuesta es casi instantánea. Como puedes ver, la primera solución es mucho más intuitiva y elegante, aunque a costa de la velocidad de ejecución para valores altos.

Por cierto, que estas funciones funcionan correctamente hasta el término número 46 inclusive (47 con tipo unsigned). A partir de aquí, con enteros de 32 bits, ya tenemos problemas de desbordamiento y empiezan a aparecer soluciones sin sentido. Si necesitas ir más allá, tendrás que utilizar enteros de 64 bits (si tu compilador dispone de ellos), o pasar a tipos float o double.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

C Relación con la Sucesion Fibonacci

Publicado por Juan (1 intervención) el 13/06/2012 03:20:19
Gracias por la respuesta!

Ahora estoy empezando a leer un poco más sobre las funciones recursivas, veo que estaba en un error y me deje llevar.

Y tienes razón, el primer codigo usando la función recursiva se puede ver más entendible y elegante, aunque a costa de recursos, de nuevo gracias por tu respuesta, me sirve de mucho. Saludos!
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar