Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Beginner Web en 21 Junio 2018, 23:13 pm


Título: Pequeña duda Fibonacci TDA Pila
Publicado por: Beginner Web en 21 Junio 2018, 23:13 pm
Hola, estoy en una duda con acerca de la serie de Fibonacci, me piden ingresar un numero y que me devuelva el termino de la serie 1,1,2,3,5,8.. utilizando pilas, no se me da la idea de como lo puedo hacer respetando operaciones del TDA Pila

Código
  1. #include <iostream>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. const int TAMPILA=32;
  7. typedef int contenedor[TAMPILA];
  8. typedef struct{
  9. 	contenedor datos;
  10. 	int cima;
  11. }tpila;
  12.  
  13. void fibonacci(int n);
  14. void init_stack(tpila &pila);
  15. void push_stack(tpila &pila, int nuevo);
  16. bool full_stack(tpila pila);
  17. bool empty_stack(tpila pila);
  18. int pop_stack(tpila &pila);
  19. int top_stack(tpila pila);
  20.  
  21. void ingreso(int n);
  22. int main()
  23. {
  24. 	int numero;
  25. 	cout << "Ingrese un numero: ";
  26. 	cin >> numero;
  27. 	fibonacci(numero);
  28. 	system("pause");
  29. 	return 0;
  30. }
  31.  
  32.  
  33. void fibonacci(int n)
  34. {
  35. 	tpila pila;
  36. 	init_stack(pila);
  37. 	while(n>0){
  38. 	//Aca pondria mi algoritmo si tuviera uno
  39. 	}
  40.  
  41. 	cout << "\nFibonacci: " << << endl;
  42. }
  43.  
  44. void init_stack(tpila &pila)
  45. {
  46. 	pila.cima=-1;
  47. }
  48.  
  49. void push_stack(tpila &pila, int nuevo)
  50. {
  51. 	if(full_stack(pila)==true){
  52. 		cout << "PILA LLENA" << endl;
  53. 	}
  54. 	else{
  55. 		pila.cima++;
  56. 		pila.datos[pila.cima]=nuevo;	
  57. 	}
  58. }
  59.  
  60. bool full_stack(tpila pila)
  61. {
  62. 	return pila.cima==TAMPILA-1;
  63. }
  64.  
  65. bool empty_stack(tpila pila)
  66. {
  67. 	return pila.cima==-1;
  68. }
  69.  
  70. int pop_stack(tpila &pila)
  71. {
  72. 	int aux;
  73. 	if(empty_stack(pila)==true){
  74. 		aux=-1;
  75. 	}
  76. 	else{
  77. 		aux=pila.datos[pila.cima];
  78. 		pila.cima--;
  79. 	}
  80. 	return aux;
  81. }
  82.  
  83. int top_stack(tpila pila)
  84. {
  85. 	int aux;
  86. 	if(empty_stack(pila)==true){
  87. 		aux=-1;
  88. 	}
  89. 	else{
  90. 		aux=pila.datos[pila.cima];
  91. 	}
  92. 	return aux;
  93. }
  94.  

Título: Re: Pequeña duda Fibonacci TDA Pila
Publicado por: SrMcLister en 22 Junio 2018, 15:04 pm
Buenas Begginer.
No me he parado a leer tu código pero lo que supongo que necesitas es un camino por el que dirigirte para llegar a la solución.
El TAD pila, que es en el que estás basando tu forma de hacer Fibonacci, funciona de tal modo que tu vas apilando numeros y solo puedes sacar el ultimo elemento.
Así mismo, Fibonacci, yo lo que haría sería:


Código:

  Guardo 1 en una variable.

  Mientras la pila no esté llena.
        Inserto en pila el valor guardado.
        Nuevo valor = Inserto + Guardado.
        Guardado = Nuevo valor.


Y para mostrar:

Código:

  Mientras el tamaño de la pila sea > 0
         std::cout de Desapilar


No se si me he explicado pero soy "begginer" como tu, solo te doy una idea, si quieres código espera a que alguien responda mejor ^^.
Un Saludo

Título: Re: Pequeña duda Fibonacci TDA Pila
Publicado por: Beginner Web en 22 Junio 2018, 21:51 pm
Muchas gracias @SrMcLister, entonces mi algoritmo quedaria asi:
//Aunque no me convence del todo ya que al ingresar 1 o 2 me devuelve el valor de la pila.cima y no es lo que busco pero funciona :D

Código
  1. int fibonacci(int n)
  2. {
  3. 	tpila pila;
  4. 	init_stack(pila);
  5. 	while(pila.cima<n-1){ 
  6. 		push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]);
  7. 	}
  8. 	return top_stack(pila);
  9. }
  10.  

En este ejemplo hago una serie 3,5,7,15,27,49,91... y aqui si me convence de lo que estoy devolviendo como valor de la pila.datos[pila.cima]

Código
  1. int serie(int n)
  2. {
  3. 	tpila pila;
  4. 	init_stack(pila);
  5. 	if(pila.cima>n-1){
  6. 		while(pila.cima>n-1){
  7. 			pop_stack(pila);
  8. 		}
  9. 	}
  10. 	else{
  11. 		while(pila.cima<n-1){
  12. 			push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]+pila.datos[pila.cima-2]);
  13. 		}
  14. 	}
  15. 	return top_stack(pila);	
  16. }
  17.  

Y no soy Beginner sino que soy malaso en matematicas y hablo  de muy malo  :laugh:

Título: Re: Pequeña duda Fibonacci TDA Pila
Publicado por: SrMcLister en 23 Junio 2018, 19:00 pm
Buenas Begginer aunque si no eres begginer ya no se como llamarte ;) jajaj..
Me alegro que te funcione, no lo probé tan solo te dije como funcionaba una pila  ;D ;D
Un Saludo!

Título: Re: Pequeña duda Fibonacci TDA Pila
Publicado por: dijsktra en 24 Junio 2018, 12:35 pm
Al Gran Fibonacci le debemos todo

Cita de: Beginner Web en 22 Junio 2018, 21:51 pm
Muchas gracias @SrMcLister, entonces mi algoritmo quedaria asi:
//Aunque no me convence del todo ya que al ingresar 1 o 2 me devuelve el valor de la pila.cima y no es lo que busco pero funciona :D

Código
  1. int fibonacci(int n)
  2. {
  3. 	tpila pila;
  4. 	init_stack(pila);
  5. 	while(pila.cima<n-1){ 
  6. 		push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]);
  7. 	}
  8. 	return top_stack(pila);
  9. }
  10.  
....

A ver: Independientemente de lo que devuelves, el errror más grande es que no "respetas" las operaciones del tad Pila... estás acceidiendo a su representación interna, cosa que el usuario que programa Fibonacci no tiene que ver....


Aquí hay dos problemas que separar
  • implementar el TAD pila
  • usar el TAD pila para resolver el problema de Fibonacci

Yo la primera, la doy por implementada en la STL, aunque es posbile que para tí sea necesario implementar la tuya propia.

Alla va mi propuesta ( tu puedes adatparla a la implementación de tu pila)
Código
  1. #include <stack> // from STL
  2. #include <algorithm> // for min
  3. #include <iostream>  // cout, cin
  4. using namespace std;
  5.  
  6.  
  7. /*
  8.  
  9. Starting on 0!
  10.  
  11. P : 0 <= N ... 
  12. I :
  13.    0 <= n <= N
  14.    top(stack) = fib(n)
  15.    n > 1 -> top (pop(stack)) = fib(n-1)
  16.  
  17.  */
  18. int Fibonacci(const int N)
  19. {
  20.   stack<int> s ;
  21.   s.push(1);
  22.   s.push(1);
  23.   for(int n=min(N,1) ;  n<N ; n++)
  24.     {
  25.     int n1= s.top() ;
  26.     s.pop();
  27.     int n2 = s.top();
  28.     s.pop();
  29.     s.push(n1);
  30.     s.push(n2+n1);
  31.     }
  32.   return s.top();
  33. }
  34.  
  35.  
  36. #define MAX 10000
  37. int main(int argc, char **args)
  38. {
  39.   int N;
  40.   for (; cin >> N  ; ) cout << Fibonacci(N) << endl;
  41.   return 0;
  42. }


Y algunos casos de prueba.

  • Las lineas 2,4,6,8,10,12... revelan la secuencia de Fibonacci
    1,1,2,3,5,8,13,21,34
  • Las lineas 1,3,5,7,9,11... revelan el orden de los términos de aquellas
    0,1,2,3,4,5,6,7,8
Código
  1. 0
  2. 1
  3. 1
  4. 1
  5. 2
  6. 2
  7. 3
  8. 3
  9. 4
  10. 5
  11. 5
  12. 8
  13. 6
  14. 13
  15. 7
  16. 21
  17. 8
  18. 34



Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines