/* Fibonacci[N] gia N<=45, 
   anadromikh kai epanalhptikh synarthsh
   f(i-1), f(i), f(i+1) fib arithmoi 
   0,1,1,2,3,5,8,13, ..... */
#include <iostream>
using namespace std;
int Fib(int); // prwtotype
int FibRec(int); // prwtotype anadromikh synarthsh

int main(int argc, char *argv[])
{ int n, ans; 
  cout<<"Dose to deikth N tou arithmou \n";
  cout<<"pou anazhtame sthn akolou8ia Fib: ";
  cin>>n;
  ans=Fib(n);
  cout << "O "<<n<<"-os Fibonacci (epanalhptika) einai o " <<ans<<endl;
  ans=FibRec(n);
  cout << "O "<<n<<"-os Fibonacci (anadromika) einai o " <<ans<<endl;  
  system("Pause");
  return 0;
}
// epanalhptikh synarthsh
int Fib(int n)
{ int i, fn_2=0, fn_1=1, fn=1;
  i=2; // Trexwn deikths arithmou Fib sthn akolouthia
  while (i != n)
   { fn_2=fn_1;
     fn_1=fn;
     fn=fn_2+fn_1;
     i++;
   }
return fn;
}
// anadromikh synarthsh
int FibRec(int n)
{ if (n==0) return 0;
  else if (n==1) return 1;
       else return (Fib(n-2)+Fib(n-1));
}