/* Calcul de Fibonacci                         */
/* Evaluation du temps d'execution             */  

public class TestFibonacci {
  
/////////////////////////////////////////////////

/* Calcul de Fib(n) par methode recursive       */
/*  - Fib(0) = 0                                */
/*  - Fib(1) = 1                                */
/*  - Fib(n) = Fib(n-1)+Fib(n-2)                */

  static long fibonacciRecursif(int n) {
    long res;
    switch (n) {
      case 0 :
      case 1 : {
        res = n; }
        break;
      default : {
        res = fibonacciRecursif(n-1)+fibonacciRecursif(n-2); }
        break; }
    return res;
  }

/* Calcul de Fib(n) par methode sequentielle   */
/*  - Fib(0) = 0                               */
/*  - Fib(1) = 1                               */
/*  - Fib(n) = Fib(n-1)+Fib(n-2)               */

  static long fibonacciSequentiel(int n) {
    long res;
    long a;
    long b;
    switch (n) {
      case 0 :
      case 1 : {
        res = n; }
        break;
      default : {
        res = 0;
        a = 0;
        b = 1;
        for ( int i = 2 ; i <= n ; i++ ) {
          res = a+b;
          a = b;
          b = res; } }
        break; }
    return res;
  }

  static void testsRapiditeEnSequentiel(int temps,int ni,int nf,int inc) {
    long i;
    long ti;
    long t;
    long n;
    Ecran.formater("%6s","Niveau");
    Ecran.formater("%21s","Resultat");
    Ecran.formater("%12s","Appels");
    Ecran.formater("%14s","Temps total");
    Ecran.formater("%14s","Temps moyen");
    Ecran.formater("%14s\n","o(n)");
    for ( int nu = ni ; nu <= nf ; nu = nu+inc ) {
      n = fibonacciSequentiel(nu);
      i = 0;
      Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur();
      minuteur.temps = temps*1000;
      minuteur.lancement();
      ti = System.nanoTime();
      do {
        fibonacciSequentiel(nu);
        i++; }
      while ( minuteur.enCours );
      t = System.nanoTime()-ti;
      Ecran.formater("%6d",nu);
      Ecran.formater("%21d",n);
      Ecran.formater("%12d",i);
      Ecran.formater("%14d",t);
      Ecran.formater("%14d",t/i);
      double rp =(double)t/i/nu;
      Ecran.formater("%14.4f\n",rp); }
  }

  static void testsRapiditeEnRecursif(int temps,int ni,int nf,int inc) {
    long i;
    long ti;
    long t;
    long n;
    Ecran.formater("%6s","Niveau");
    Ecran.formater("%21s","Resultat");
    Ecran.formater("%12s","Appels");
    Ecran.formater("%14s","Temps total");
    Ecran.formater("%14s","Temps moyen");
    Ecran.formater("%14s\n","o(n*log(n))");
    for ( int nu = ni ; nu <= nf ; nu = nu+inc ) {
      n = fibonacciRecursif(nu);
      i = 0;
      Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur();
      minuteur.temps = temps*1000;
      minuteur.lancement();
      ti = System.nanoTime();
      do {
        fibonacciRecursif(nu);
        i++; }
      while ( minuteur.enCours );
      t = System.nanoTime()-ti;
      Ecran.formater("%6d",nu);
      Ecran.formater("%21d",n);
      Ecran.formater("%12d",i);
      Ecran.formater("%14d",t);
      Ecran.formater("%14d",t/i);
      double rp =(double)t/i/n;
      Ecran.formater("%14.4f\n",rp); }
  }

/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    int temps;
    int ni;
    int nf;
    int inc;
    Ecran.afficher("Nombre de secondes de test? ");
    temps = Clavier.saisirInt();
    Ecran.afficher("Niveau initial?   ");
    ni = Clavier.saisirInt();
    Ecran.afficher("Niveau de fin ?   ");
    nf = Clavier.saisirInt();
    Ecran.afficher("Increment     ?   ");
    inc = Clavier.saisirInt();
    testsRapiditeEnSequentiel(temps,ni,nf,inc);
    testsRapiditeEnRecursif(temps,ni,nf,inc);
  }
}