#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream.h>

// pour le chronometrage de fibonacci
#include <time.h>

// prototypes des fonctions
void   Exo_Binomiaux(int n,int k);
void   Exo_Fibonacci(int n);
void   Exo_Syracuse(void);

// le main
int    main(int argc,char* argv[])
{
  int n;
  int k;

  cout << "binomial de (ici n>=k): n? ";
  cin >> n;
  cout << "k? ";
  cin >> k;
  Exo_Binomiaux(n,k);
  cout << endl << endl;

  cout << "fibonacci de ? ";
  cin >> n;
  Exo_Fibonacci(n);
  cout << endl << endl;

  Exo_Syracuse();
  cout << endl << endl;

  return 0;
}



// exo 1.1

int    Binomial(int n,int k)
{
  if ( k <= 0 || k >= n ) return 1;
  return Binomial(n-1,k)+Binomial(n-1,k-1);
}


void   Exo_Binomiaux(int n,int k)
{
  if ( n <= 0 || k < 0 || n < k ) {
    cout << "calcul impossible\n";
    return;
  } else {
    cout << "binomial de " << n << " | " << k << " : " << Binomial(n,k) << endl;
  }
}


// exo 1.2
// version recursive
int    Rec_Fibonacci(int n)
{
  if ( n <= 1 ) return 1;
  return Rec_Fibonacci(n-1)+Rec_Fibonacci(n-2);
}

// version iterative
//la version iterative est bien sur beaucoup plus rapide, en effet le calcul de fib(5)
//en recursif se decompose :
//fib(5)=fib(4)+fib(3)
//  fib(4)=fib(3)+fib(2)
//    fib(3)=fib(2)+fib(1)
//    fib(2)=fib(1)+fib(0)
//      fib(1)=1
//      fib(0)=1
//  fib(3)=fib(2)+fib(1)
//    fib(2)=fib(1)+fib(0)
//      fib(1)=1
//      fib(0)=1
//    fib(1)=1
//On aura donc calcule 2 fois fib(0), 3 fois fib(1), 2 fois fib(2), 2 fois fib(3)...
int    Ite_Fibonacci(int n)
{
  // ici a=fn et b=fn-1
  int    a=1,b=1;
  if ( n <= 1 ) return 1;
  for (int i=2;i<=n;i++) {
    // calcul de fi
    int val=a+b;
    // on decale
    b=a;
    a=val;
  }
  return a;
}

void   Exo_Fibonacci(int n)
{
  if ( n < 0 ) {
    cout << "valeur non definie\n";
    return;
  }
  cout << "fibonacci(" << n << ")= " << Ite_Fibonacci(n) << endl;

  // chronometrages
  {
    time_t depart=time(NULL);  // temps de depart
    // le calcul
    for (int i=0;i<10000;i++) {
      Ite_Fibonacci(n);
    }
    time_t fin=time(NULL);
    time_t duree=fin-depart;
    cout << "10000 calculs (version iterative) prennent " << duree << " secondes\n";
  }
  {
    time_t depart=time(NULL);  // temps de depart
    // le calcul
    for (int i=0;i<10000;i++) {
      Rec_Fibonacci(n);
    }
    time_t fin=time(NULL);
    time_t duree=fin-depart;
    cout << "10000 calculs (version recursive) prennent " << duree << " secondes\n";
  }
}

// exo 1.3
int    syrac(int un)
{
  if ( un%2 == 0  ) {
    return un/2;
  } else {
    return (3*un+1)/2;
  }
  return 0;
}
// duree du vol=1+duree du vol a partir du suivant
int    DureeVol(int un)
{
  if ( un == 1 ) return 0;
  return 1+DureeVol(syrac(un));
}
// altitude=max(un,altitude a partir du suivant)
int    AltitudeVol(int un)
{
  if ( un == 1 ) return 1;
  int  altSuiv=AltitudeVol(syrac(un));
  return (un>altSuiv)?un:altSuiv;
}
// les calculs
void   Exo_Syracuse(void)
{
  // maximums des durees et altitudes
  {
    int    dureeMax=0,argDureeMax=-1;
    int    altitudeMax=0,argAltitudeMax=-1;
    for (int i=1;i<=1000;i++) {
      int  d=DureeVol(i);
      int  a=AltitudeVol(i);
      if ( d > dureeMax ) {
	dureeMax=d;
	argDureeMax=i;
      }
      if ( a > altitudeMax ) {
	altitudeMax=a;
	argAltitudeMax=i;
      }
    }
    cout << "duree de vol maximum= " << dureeMax << " pour i= " << argDureeMax << endl;
    cout << "altitude de vol maximum= " << altitudeMax << " pour i= " << argAltitudeMax << endl;
  }
  // durees et altitude records
  {
    cout << "records:\n";
    int    dureeMax=0;
    int    altitudeMax=0;
    for (int i=1;i<=1000;i++) {
      int  d=DureeVol(i);
      int  a=AltitudeVol(i);
      if ( d > dureeMax ) {
	dureeMax=d;
	cout << "  record de duree " << d << " pour " << i << endl;
      }
      if ( a > altitudeMax ) {
	altitudeMax=a;
	cout << "  record d'altitude " << a << " pour " << i << endl;
      }
    }
  }
  // durees de vol de longeur k
  {
    cout << "plus petits entiers de duree de vol...\n";
    for (int k=1;k<=20;k++) {
      cout << "   k : ";
      int i;
      for (i=1;i<1000;i++) {
	if ( DureeVol(i) == k ) {
	  cout << i << endl;
	  break;
	}
      }
      if ( i >= 1000 ) {
	cout << "pas trouve\n";
      }
    }
  }
}