/* Recursivite en arbre n-aire parfait         */
/* Evaluation du temps d'execution             */

public class TestRecursiviteEnArbreParfaitEnConsole {

/////////////////////////////////////////////////

/* Parcours recursif en arbre unaire           */
/* de profondeur n                             */

  static long parcoursUnaire(int n) {
    long nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursUnaire(n-1); }
    return nb;
  }

/* Parcours recursif en arbre binaire parfait  */
/* de profondeur n                             */

  static long parcoursBinaire(int n) {
    long nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursBinaire(n-1);
      nb = nb+parcoursBinaire(n-1); }
    return nb;
  }

/* Parcours recursif en arbre ternaire parfait */
/* de profondeur n                             */

  static long parcoursTernaire(int n) {
    long nb = 1;
    if ( n > 0 ) {
      nb = nb+parcoursTernaire(n-1);
      nb = nb+parcoursTernaire(n-1);
      nb = nb+parcoursTernaire(n-1); }
    return nb;
  }

/* Parcours recursif en arbre parfait d'arite  */
/* quelconque et de profondeur n               */

  static long parcoursNaire(int n,int arite) {
    long nb = 1;
    if ( n > 0 ) {
      for ( int i = 0 ; i < arite ; i++ ) {
        nb = nb+parcoursNaire(n-1,arite); } }
    return nb;
  }

  static void testsEnUnaire(int temps,int ni,int nf,int inc) {
    Console.formater("%8s%12s%14s%14s%22s%14s\n",
                   "Niveau","Appels","Temps total","Temps total",
                   "Temps moyen","o(n)");
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
        mntr.temps = temps*1000;
        mntr.lancement();
        long i = 0;
        long ti = System.nanoTime();
        do {
          parcoursUnaire(n);
          i++; }
        while ( mntr.enCours );
        long t = System.nanoTime()-ti;
        Console.formater("%8d%12d%14d%14d%22.3f%14.4f\n",
                       n,i,t,mntr.dt,(double) t/i,((double) t/i)/n); }
      System.gc(); }
  }

  static void testsEnBinaire(int temps,int ni,int nf,int inc) {
    Console.formater("%8s%12s%14s%22s%14s\n",
                   "Niveau","Appels","Temps total",
                   "Temps moyen","o(2^n)");
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
        mntr.temps = temps*1000;
        mntr.lancement();
        long i = 0;
        long ti = System.nanoTime();
        do {
          parcoursBinaire(n);
          i++; }
        while ( mntr.enCours );
        long t = System.nanoTime()-ti;
        Console.formater("%8d%12d%14d%22.3f%14.4f\n",
                       n,i,t,(double) t/i,
                       ((double) t/i)/Math.pow(2,n)); }
      System.gc(); }
  }

  static void testsEnTernaire(int temps,int ni,int nf,int inc) {
    Console.formater("%8s%12s%14s%22s%14s\n",
                   "Niveau","Appels","Temps total",
                   "Temps moyen","o(3^n)");
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      { Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
        mntr.temps = temps*1000;
        mntr.lancement();
        long i = 0;
        long ti = System.nanoTime();
        do {
          parcoursTernaire(n);
          i++; }
        while ( mntr.enCours );
        long t = System.nanoTime()-ti;
        Console.formater("%8d%12d%14d%22.3f%14.4f\n",
                       n,i,t,(double) t/i,
                       ((double) t/i)/Math.pow(3,n)); }
      System.gc(); }
  }

  static void testsEnNaire(int temps,int ni,int nf,int inc,int arite) {
    Console.formater("%8s%12s%14s%22s%14s\n",
                   "Niveau","Appels","Temps total",
                   "Temps moyen","o(arite^n)");
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
      mntr.temps = temps*1000;
      mntr.lancement();
      long i = 0;
      long ti = System.nanoTime();
      do {
        parcoursNaire(n,arite);
        i++; }
      while ( mntr.enCours );
      long t = System.nanoTime()-ti;
      System.gc();
      Console.formater("%8d%12d%14d%22.3f%14.4f\n",
                     n,i,t,(double) t/i,
                     ((double) t/i)/Math.pow(arite,n)); }
  }

/////////////////////////////////////////////////

/* Programme principal                         */

  public static void main(String [] args) {
    Console.setTitle("TestRecursiviteEnArbreParfait");
    //Console.afficher("Nombre de secondes de test? ");
    //int temps = Console.saisirInt();
    //Console.afficherln("Arité 10");
    //testsEnNaire(temps,0,10,1,10);
    //Console.afficherln("Ternaire");
    //testsEnTernaire(temps,0,25,1);
    //Console.afficherln("Binaire");
    //testsEnBinaire(temps,0,40,1);

    //Console.afficherln("Unaire");
    //testsEnUnaire(10,0,10,1);
    //testsEnUnaire(10,11,50,1);

    //Console.afficherln("Binaire");
    //testsEnBinaire(60,0,40,1);
    //Console.afficherln("Ternaire");
    //testsEnTernaire(60,0,25,1);
    Console.afficherln("Unaire");
    testsEnUnaire(60,0,500,1);
    //testsEnUnaire(60,0,5000,10);
    //testsEnUnaire(60,0,100000,1000);
    //testsEnUnaire(60,0,10000000,100000);
    //testsEnUnaire(60,500,1000,1);
    //testsEnUnaire(60,5000,10000,10);
  }
}