#include<iostream>
#include<time.h>

#define MAX_FIBO 10000

double Fibos[MAX_FIBO]={0,1};

double fibonacci(unsigned int n);
double fibonacci_dp(unsigned int n);

int main(int argc, char **argv){

  unsigned int k;
  clock_t prima, dopo;
  double f;

  cout << "\n\n\nInserisci un numero positivo: ";
  cin >> k;
 

  prima=clock();
  f=fibonacci_dp(k);
  dopo=clock();
  
  cout << f << " (Clock: " << (int)(dopo-prima) << ")\n";

  prima=clock();
  f=fibonacci(k);
  dopo=clock();
  
  cout << f << " (Clock: " << (int)(dopo-prima) << ")\n";

  return 0;
}

double fibonacci(unsigned int n){
  if(!n)return 0;
  if(n==1)return 1;
  return fibonacci(n-1)+fibonacci(n-2);
}


double fibonacci_dp(unsigned int n){
  if(!n)return 0;
  if(Fibos[n])return Fibos[n];
  return Fibos[n]=fibonacci_dp(n-1)+fibonacci_dp(n-2);
}