1

introducir la descripción de la imagen aquí

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 */
0

1 respuesta 1

1

¿ Como bajar la memoria en RAM que utiliza un programa en C/C++ ?

Pues, normalmente, lo mas fácil es no usarla :-)

En tu caso concreto, no es necesario mantener una lista para calcular la sucesión. Tu programa se invoca, procesa, y muere. Generar una lista y recorrerla va a ocuparte mucho mas tiempo y consumirá infinitamente mas memoria que simplemente calcular los elementos de la sucesión cada vez:

#include <iostream>

int main( ) {
    int prev = 0, curr = 1, index = 1, toLocate;

    std::cout << "Numero ? ";
    std::cin >> toLocate;

    if( toLocate == 0 ) {
        index = 0;
    } else if( toLocate == 1 ) {
    } else {
        while( true ) {
            int suma  = prev + curr;
            ++index;
            if( suma > toLocate ) {
                index = -1;
                break;
            }

            if( suma == toLocate ) { break; }

            prev = curr;
            curr = suma;
        }
    }

    if( index == -1 ) {
        std::cout << "No se encuentra\n";
    } else {
        std::cout << "Indice: " << index << '\n';
    }

    return 0;
}

Observa que no se ha tratado el caso especial 1. Dicho número ocupa las posiciones 1 y 2 de la lista.
Tampoco se ha tratado el caso del desbordamiento, que puede suceder si la suma del elemento actual + el anterior no cabe en un entero.

Estas mejoras quedan a tu libre disposición.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.