Descripción
Como ya sabemos la sucesión de fibonacci esta compuesta por los números: 1, 1, 2, 3, 5, 8, 13, 21, 34. . . Sabiendo esto la tarea es dado un numero N debes encontrar la posición que ocupa en la sucesión de fibonacci.
Entrada
Un numero N solamente
Salida
Un único entero que indique en que posición se encuentra el numero en la sucesión. Si el numero no se encuentra en la sucesión imprimir un -1.
Ejemplos
Entrada 1 - Salida 1
Entrada 2 - Salida 3
Entrada 3 - Salida 4
Entrada 1000 - Salida -1
**Mi codigo que excede los 8MB de megas de memoria :( **
#include<iostream>
using namespace std;
/* Estructuras para generar nodos */
struct Nodo
{
short dato;
//short indice;
struct Nodo *sig;
}typedef Nodo;
/* Estructuras para generar listas de nodos */
struct Lista
{
short tam;
Nodo *ini;
Nodo *fin;
}typedef Lista;
/* Prototipos de la funciones */
Lista * crearLista();
Nodo * crearNodo(short dato);
short addNodoALista(Nodo *nvoNodo, Lista *miLista);
void imprimirLista(Lista *miLista);
void fibonacciGen(Lista *miLista, short N);
short busquedaBinaria(short miNum, Lista *miLista);
/* Variables globales */
Lista *fibonacciNum = NULL;
short N;
int main()
{
cin >> N;
fibonacciNum = crearLista();
fibonacciGen(fibonacciNum, N);
cout << busquedaBinaria(N, fibonacciNum) << "\n";
delete fibonacciNum;
return 1;
}
short busquedaBinaria(short miNum, Lista *miLista)
{
short min = 0;
short max = miLista->tam - 1;
while(min <= max) {
short mitad = (min + max)/2;
if((miLista->ini + mitad)->dato == miNum)
return mitad + 1;
else if((miLista->ini + mitad)->dato < miNum)
min = mitad + 1;
else
max = mitad - 1;
}
return -1;
}
void fibonacciGen(Lista *miLista, short N)
{
short num = 1, ant = 0, aux;
while(num <= N){
addNodoALista(crearNodo(num), miLista);
aux = num;
num += ant;
ant = aux;
}
}
/* Empiezan funciones de lista enlazadas */
void imprimirLista(Lista *miLista)
{
if(miLista->ini != NULL) {
Nodo *aux = miLista->ini;
while(aux != NULL) {
//printf("indice: %3d, Dato: %3d\n",aux->indice, aux->dato);
aux = aux->sig;
}
}
}
short addNodoALista(Nodo *nvoNodo, Lista *miLista)
{
// if (nvoNodo != NULL && miLista != NULL)
// nvoNodo->indice = miLista->tam;
if (miLista->ini == NULL) {
miLista->fin = miLista->ini = nvoNodo;
}else{
miLista->fin->sig = nvoNodo;
miLista->fin = miLista->fin->sig;
}
miLista->tam++;
return 1;
}
Nodo * crearNodo(short dato)
{
Nodo *miNodo = new Nodo();
miNodo->dato = dato;
miNodo->sig = NULL;
return miNodo;
}
Lista * crearLista()
{
Lista *miLista = new Lista();
miLista->tam=0;
miLista->ini = NULL;
miLista->fin = NULL;
return miLista;
}
/* Terminan funciones de lista enlazadas */