LA DICHOTOMIE.
Une mthode dichotomique (du grec dikhotomia = action de partager
en deux) est une mthode algorithmique de recherche o chaque tape on
coupe l'espace de recherche en deux parties pas forcment gales, le
but tant de diminuer l'espace de recherche, c'est un principe
ancien.On retrouve une trace de ce principe dans la Grce antique
par l'intermdiaire d'un paradoxe de Znon.
On peut appliquer la mthode de la dichotomie trois types de
problmes :
1-Introduction par la recherche d'un nombre inconnu.
Objectif : Faire merger la mthode par dichotomie laide du jeu :
dterminer le plusrapidement un entier choisi arbitrairement entre 1
et 100 par lordinateur .
a) Etape 1 : le jeu .Le principe est celui d'un jeu : une
personne choisit un nombre au hasard entre 1 et 100 .1)Programmer
l'aide d'algobox, lalgorithme Devine_nombre :1 VARIABLES2
nb_inconnu EST_DU_TYPE NOMBRE3 nb_coups EST_DU_TYPE NOMBRE4
nb_propose EST_DU_TYPE NOMBRE5 DEBUT_ALGORITHME6 nb_coups
PREND_LA_VALEUR 17 nb_inconnu PREND_LA_VALEUR round(99*random())+18
AFFICHER "Proposez une valeur pour le nombre inconnu."9 LIRE
nb_propose10 TANT_QUE (nb_inconnu!=nb_propose) FAIRE11
DEBUT_TANT_QUE12 nb_coups PREND_LA_VALEUR nb_coups+113 SI
(nb_inconnu>nb_propose) ALORS14 DEBUT_SI15 AFFICHER "Votre
nombre est plus petit que le nombre inconnu."16 FIN_SI17 SINON18
DEBUT_SINON19 AFFICHER "Votre nombre est plus grand que le nombre
inconnu."20 FIN_SINON21 AFFICHER "Proposez une autre valeur pour le
nombre inconnu."22 LIRE nb_propose25 FIN_TANT_QUE26 AFFICHER "Gagn
en "27 AFFICHER nb_coups28 AFFICHER " coups !"29 FIN_ALGORITHME
2)Le tester
b) Etape 2 : l'algorithme qui automatise la dmarche.
On propose d'automatiser la dmarche de recherche l'aide d'un
algorithme.Voici un algorithme incomplet.1 VARIABLES2 nb_inconnu
EST_DU_TYPE NOMBRE3 nb_propose EST_DU_TYPE NOMBRE4 a EST_DU_TYPE
NOMBRE5 b EST_DU_TYPE NOMBRE6 nb_coups EST_DU_TYPE NOMBRE7
DEBUT_ALGORITHME8 nb_inconnu PREND_LA_VALEUR round(99*random())+19
a PREND_LA_VALEUR 110 b PREND_LA_VALEUR 10011 nb_coups
PREND_LA_VALEUR 112 TANT_QUE (b>a+1) FAIRE13 DEBUT_TANT_QUE14
nb_coups PREND_LA_VALEUR nb_coups+115 nb_propose PREND_LA_VALEUR
floor((a+b)/2)16 SI (nb_proposef(mil) le maximum est dans
l'intervalle [a; mil] qui a pour milieu q1;
Si f(q2)>f(mil) le maximum est dans l'intervalle [mil;b] qui a
pour milieu q2 ;
si aucun des cas prcdents ne se produit, le maximum est dans
l'intervalle [q1;q2] qui a pour milieu mil.
On recommence au dbut et on s'arrte lorsque le longueur de
l'intervalle obtenu est infrieur la prcision choisie,
l'approximation du nombre o le maximum est atteint sera donn par le
centre du dernier intervalle obtenu.
Schma :
Exercice :
crire cet algorithme en langage naturel.Adapter cet algorithme
la recherche d'un minimum.Utiliser, si besoin est, ces algorithmes,
l'aide d'Algobox, pour dterminer les extrema deformule
;formule;formule.
