import Tableau;


class Recursivite
{
    /**
     * Calcule la factorielle de maniere recursive
     * @param n entier dont calculer la factorielle
     * @return la factorielle de n
     */  
	
    public static int factorielle (int n) {
	if (n <= 0)
	    return(0);
	else
	    return n * factorielle(n-1);
    }


    /**
     * Calcule la division entiere par 2 de m sans utiliser /
     * de maniere recursive
     * @param m nombre a diviser par 2
     * @return la division entiere de m par 2
     */  

    public static int division2Rec(int m) {
	if (m <= 1)
	    return(0);
	else
	    return(1 + division2Rec(m-2));
    }


    /**
     * Calcule la multiplication entiere de m par n sans utiliser *
     * de maniere recursive
     * @param m nombre a multiplier par n
     * @param n nombre a multiplier par m
     * @return la multiplivcation entiere de m par n
     */ 

    public static int multiplicationRec(int m, int n) {
	if (n < 0) {
	    // Si n est negatif, on multiplie m et n par -1
	    // sinon n ne decroissera pas jusqu'a 0
	    return multiplicationRec(-m, -n);
	}
	if (n == 0)
	    return 0;
	else
	    return (m + multiplicationRec(m, n-1));
    }


    /**
     * Calcule le coefficient binomial C_n^p de maniere recursive
     * @param n
     * @param p
     * @return le coefficient binomial C_n^p 
     */  

    public static long binomial (int n, int p) {
	if ((n < p) || (n < 0) || (p < 0))
	    return 0 ;
	else if ((p == 0) || (p == n))
	    return 1 ;
	else
	    return binomial (n-1, p-1) + binomial (n-1, p) ;
    }


    /**
     * Recherche la valeur e dans le tableau suppose trie t 
     * entre les indices g et d
     * @param t tableau trie
     * @param g borne gauche a partir de laquelle rechercher e
     * @param d borne droite jusqu'ou rechercher e
     * @param e element a rechercher
     * @return l'indice ou e a ete trouve et -1 sinon
     */

    public static int rechercheDicho(Tableau t, int g, int d, int e) {
	int k;

	if (g > d)
	    return -1;

	k = (g+d)/2;

	if ((t.getContenu())[k]==e) 
	    return(k);
        if (e < (t.getContenu())[k]) 
	    return(rechercheDicho(t,g,k-1,e));
        else 
	    return(rechercheDicho(t,k+1,d,e));
    }


    /**
     * Tours de Hanoi
     * Affiche les deplacements a effectuer pour deplacer N disques
     * des tiges src a dest en utilisant inter comme intermediaire
     * @param N nombre de disques a deplacer
     * @param src tige ou se trouve les disques
     * @param inter tige intermediaire pour deplacer les disques
     * @param dest tige ou doivent se trouver les disques a l'arrivee
     */  

    public static void déplacerTour (int N, char src, char inter, char dest) {
	if (N > 0) {
	    déplacerTour (N - 1, src, dest, inter) ;	// src --> inter
	    System.out.println ("Disque " + N + " de " + src + " vers " + dest) ;		
	    déplacerTour (N - 1, inter, src, dest) ;	// inter --> dest
	}
    }


    public static void main (String [] args) {
	int N = 3, res;
	Tableau t = new Tableau(10,10);

	if (args.length > 0)
	    N = Integer.parseInt(args[0]) ;
		
	res = rechercheDicho(t, 0, t.getTaille(), N);
	if (res == -1)
	    System.out.println(N + " n'a pas ete trouve dans " + t);
	else
	    System.out.println(N + " a  ete trouve dans " + t + " a l'indice " + res);
	    
	// A : tige de gauche
	// B : tige du milieu
	// C : tige de droite
		
	déplacerTour(N, 'A', 'B', 'C');

	System.exit (0) ;
    }
}