Pequeña duda Fibonacci TDA Pila

[Beginner Web]

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 (cpp) [Seleccionar] Expandir


#include <iostream>
#include <math.h>

using namespace std;

const int TAMPILA=32;
typedef int contenedor[TAMPILA];
typedef struct{
contenedor datos;
int cima;
}tpila;

void fibonacci(int n);
void init_stack(tpila &pila);
void push_stack(tpila &pila, int nuevo);
bool full_stack(tpila pila);
bool empty_stack(tpila pila);
int pop_stack(tpila &pila);
int top_stack(tpila pila);

void ingreso(int n);
int main()
{
int numero;
cout << "Ingrese un numero: ";
cin >> numero;
fibonacci(numero);
system("pause");
return 0;
}


void fibonacci(int n)
{
tpila pila;
init_stack(pila);
while(n>0){
//Aca pondria mi algoritmo si tuviera uno
}

cout << "\nFibonacci: " << << endl;
}

void init_stack(tpila &pila)
{
pila.cima=-1;
}

void push_stack(tpila &pila, int nuevo)
{
if(full_stack(pila)==true){
cout << "PILA LLENA" << endl;
}
else{
pila.cima++;
pila.datos[pila.cima]=nuevo;
}
}

bool full_stack(tpila pila)
{
return pila.cima==TAMPILA-1;
}

bool empty_stack(tpila pila)
{
return pila.cima==-1;
}

int pop_stack(tpila &pila)
{
int aux;
if(empty_stack(pila)==true){
aux=-1;
}
else{
aux=pila.datos[pila.cima];
pila.cima--;
}
return aux;
}

int top_stack(tpila pila)
{
int aux;
if(empty_stack(pila)==true){
aux=-1;
}
else{
aux=pila.datos[pila.cima];
}
return aux;
}


[SrMcLister]

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 [Seleccionar] Expandir



 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 [Seleccionar] Expandir



 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

[Beginner Web]

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

Código (cpp) [Seleccionar] Expandir


int fibonacci(int n)
{
tpila pila;
init_stack(pila);
while(pila.cima<n-1){
push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]);
}
return top_stack(pila);
}


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 (cpp) [Seleccionar] Expandir


int serie(int n)
{
tpila pila;
init_stack(pila);
if(pila.cima>n-1){
while(pila.cima>n-1){
pop_stack(pila);
}
}
else{
while(pila.cima<n-1){
push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]+pila.datos[pila.cima-2]);
}
}
return top_stack(pila);
}


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

[SrMcLister]

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 
Un Saludo!

[dijsktra]

Al Gran Fibonacci le debemos todo

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

Código (cpp) [Seleccionar] Expandir


int fibonacci(int n)
{
tpila pila;
init_stack(pila);
while(pila.cima<n-1){
push_stack(pila, pila.datos[pila.cima]+pila.datos[pila.cima-1]);
}
return top_stack(pila);
}

....

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 (c) [Seleccionar] Expandir


#include <stack> // from STL
#include <algorithm> // for min
#include <iostream>  // cout, cin
using namespace std;


/*

Starting on 0!

P : 0 <= N ...
I :
   0 <= n <= N
   top(stack) = fib(n)
   n > 1 -> top (pop(stack)) = fib(n-1)

*/
int Fibonacci(const int N)
{
  stack<int> s ;
  s.push(1);
  s.push(1);
  for(int n=min(N,1) ;  n<N ; n++)
    {
    int n1= s.top() ;
    s.pop();
    int n2 = s.top();
    s.pop();
    s.push(n1);
    s.push(n2+n1);
    }
  return s.top();
}


#define MAX 10000
int main(int argc, char **args)
{
  int N;
  for (; cin >> N  ; ) cout << Fibonacci(N) << endl;
  return 0;
}


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 (c) [Seleccionar] Expandir

0
1
1
1
2
2
3
3
4
5
5
8
6
13
7
21
8
34