/*
Obliczenie N-go elementu ciągu Fibonaciego.
F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2);
Rekurencja, iteracja, intelegentna rekurencija.





















*/
#include <iostream>
#include <iomanip>
#include <limits>

//using namespace std; // w starszych kompilatorach trzeba zakomentować ten wiersz

long double Fibonacci_R(unsigned short x);
long double Fibonacci_I(unsigned short x);
long double Fibonacci_IR(unsigned short x);

int main()
  {
   for(;;)
     {
      cout<<"Podaj liczbe (0-koniec) : ";
      unsigned short X;
      cin>>X;
      if(cin.good())
        {
         if(!X) break;
         cout.setf(ios::fixed);
         if(X<35) // inaczej się nie doczekamy na wynik
           {
            cout<<"F("<<X<<")="<<setprecision(0)<<Fibonacci_R(X)<<endl;
           }
         cout<<"F("<<X<<")="<<setprecision(0)<<Fibonacci_I(X)<<endl;
         cout<<"F("<<X<<")="<<setprecision(0)<<Fibonacci_IR(X)<<endl;
        }
      else
        {
         cin.clear();
         cout<<"Blad wprowadzenia"<<endl;
        }
      cin.ignore(INT_MAX,'\n');
     }
   return 0;
  }

long double Fibonacci_R(unsigned short x)
  {
   if(x<2) return(1);
   return Fibonacci_R((unsigned short)(x-1))+Fibonacci_R((unsigned short)(x-2));
  }

long double Fibonacci_I(unsigned short x)
  {
   if(x<2) return(1);
   long double f1=1;
   if(x>1)
     {
      long double f2=1;
      for(unsigned short i=2;i<=x;++i)
        {
         long double tmp=f1+f2;
         f2=f1;
         f1=tmp;
        }
     }
   return f1;
  }

long double Fibonacci_IR(unsigned short x)
  {
   if(x>=23600) return(0);
   if(x<2) return(1);
   static long double T[23600]={1,1};
   if(!T[x])
     {
      T[x]
        =
         Fibonacci_IR((unsigned short)(x-1))
         +
         Fibonacci_IR((unsigned short)(x-2))
        ;
     }
   return(T[x]);
  }