#include <iostream>
#include <vector>

#define MAX_N_FIBONACCI_ARRAY   10000
#define NO_INICIALIZADO 0

using namespace std;
vector <unsigned int> fiboVector(MAX_N_FIBONACCI_ARRAY, NO_INICIALIZADO);

unsigned int fibonacci1 (unsigned int);

unsigned fibonacci2 (unsigned int);

int main(){

    unsigned int n;

    cout << "Ingrese un numero para calcular su secuencia de Fibonacci: " << endl;
    cin >> n;

    cout << "El resultado de la secuencia de Fibonacci es: " << endl << fibonacci1(n) << endl << fibonacci2(n);
    return 0;
}

unsigned int fibonacci1(unsigned int num){
    if (num <= 1){
        return num;
    } else {
        return fibonacci1(num - 1) + fibonacci1(num - 2);

    }
}

unsigned int fibonacci2(unsigned int num){
    unsigned int x;

    if (num <= 1){
        return num;
    }

    if (fiboVector[num] == NO_INICIALIZADO) {
        x = fibonacci2(num - 1) + fibonacci2(num - 2);
        fiboVector[num] = x;
    }

    return fiboVector[num];
}