#include <stdio.h>
#include <conio.h>
#include <math.h>


//////////////////////////////////////////
double fibo( long n )
{
	double f, f0, f1;

	f = 1;
	f0 = 1;
	f1 = 1;
	for( long i = 2; i <= n; i ++ )
	{
		f = f0 + f1;
		f0 = f1;
		f1 = f;
	}
	return f;
}


//////////////////////////////////////////
double fiboRecur( long n )
{
	if( n < 2 ) return 1;
	return fiboRecur(n-1) + fiboRecur(n-2);
}


//////////////////////////////////////////
int calcFi( int n )
{
	int Fi;
	double V5 = sqrt(5);
	double part1 = pow( (1+V5)/2, n );
	double part2 = pow( (1-V5)/2, n );

	Fi = (int)( (double)(V5/5)*(part1-part2) );
	return Fi;
}


//////////////////////////////////////////
void main()
{
	double nbor = (sqrt(5) + 1)/2;

	clrscr();


	// Mise en evidence de la lenteur de l'algorithme
	// recursif
	for( int t=0; t < 30; t++ )
	{
		double test = fiboRecur( t );
		double test2 = fibo( t );
		printf( "t=%d, test=%.0f, test2=%.0f\n", t, (float)test, (float)test2 );
	}

	// Convergence vers le nombre d'or
	// Met en evidence les debordements
	for( long i = 1; i < 1475; i ++ )
	{
		double f1, f2, f2divf1;

		f1 = fibo( i-1 );
		f2 = fibo( i );
		f2divf1= f2/f1;

		printf( "fibo(%ld)=%.0f,f2/f1=%7.5f,(V5+1)/2=%7.5f\n",
			i, (float)f2, (float)f2divf1, (float)nbor );
	}

	// Calcul de la partie entiere
	// On retombe sur la suite de fibonacci
	for( int i = 0; i < 1000; i ++ )
	{
		int Fi = calcFi(i);
		printf( "Fi(%d)=%d\n", i, Fi );
	}

	getch();
}