// recherche d'un prix cache
// le programme fixe au hasard un prix compris entre 1 et 1000
// puis recherche ce prix en adoptant comme strategie de recherche une
// recherche par dichotomie
// Le programme effectue 100 parties consecutives et affiche la moyenne
// du nombre d'essais qui lui ont ete necessaires pour trouver le bon prix
// avec cette strategie

public class PrixLot2 {


  public static void main(String[] args)
    {
      int prixCherche; // le prix cache a decouvrir
      int prixPropose; // le prix propose

      int borneInf = 1;    // borne inferieure de l'intervalle de recherche
      int borneSup = 1000; // borne superieure de l'intervalle de recherche

      int nbEssais = 0;    // nombre d'essais pour trouver le prix dans une partie
      int nbTotalEssais = 0; // nombre d'essais total pour toutes les parties




      for (int i = 1; i <= 100; i++)
	{

	  borneInf = 1; borneSup = 1000;
	  // tirage au hasard de prixCherche dans l'intervalle [1 1000]
	  prixCherche = (int) (Math.random() * 1000 + 1);

	  // donne une premiere proposition de prix
	  // on prend le milieu de l'intervalle borneInf borneSup
	  prixPropose = 500;
	  nbEssais = 1;

	  while (prixPropose != prixCherche)
	    {
	      // selon la position du prixPropose, mise a jour de
              // l'intervalle de recherche
	      if (prixPropose > prixCherche)
		borneSup = prixPropose - 1;
	      else
		borneInf = prixPropose + 1;

	      // nouvelle proposition de prix
	      // le prix propose est le milieu de lintervalle de recherche
	      prixPropose = borneInf + (borneSup - borneInf)/2;
	      nbEssais++;

	    }

	  System.out.println("le programme a trouve le prix cache ("+
			     prixPropose + ") en " + nbEssais + " essais");

	  nbTotalEssais = nbTotalEssais + nbEssais;

	} 
      System.out.println("sur 100 parties le programme a trouve le prix en moyenne en " + (double) (nbTotalEssais)/100 + " essais");

    }
}