Algo : recherche dichotomique itérative

Bonjour,

depuis quelques semaines je tente de m'initier à l'algorithmique avec le livre "Apprendre à programmer" pour ensuite apprendre le Python. Je coince sur un début d'algo de "recherche dichotomique itérative" et je me sens vraiment très bête. Voici le début de la méthode en question :

Classe VecteurEntier comporte methode rechercheDicho (x:entier): entier
variables : gauche, milieu, droite : entier;
trouve : booléen;
Début
gauche <--- 0;
droite <--- taille-1;
milieu <--- (gauche+droite)/2;
trouve <--- Faux ;

tant-que ((gauche <ou= droite) ET (NON trouve)) faire
... etc..

Je ne comprends pas la condition de la boucle "tant-que". Ca veut dire quoi "NON trouve"? A ce stade ça renvoie la valeur boléenne VRAI non? Mais alors la condition se traduit comme suit : "tant-que gauche < ou = droite et vrai, faire...". Pour moi ça n'a aucun sens! Quelqu'un saurait-il m'expliquer cette condition??

Merci beaucoup beaucoup!

Sidonie

Citation:

---

Envoyé par sidonette

Ca veut dire quoi "NON trouve"? A ce stade ça renvoie la valeur boléenne VRAI non?

---

Euh non.. Ici "NON trouve" doit être pris comme une expression, pas comme une opération booléenne

trouve est un drapeau flag) intialisé à faux.


"NON trouve" signifie "trouve = faux"

Donc

Code:

---

"tant que ( (gauche <= droite) ET (trouve = faux) )

---

Citation:

---

Envoyé par sidonette

Bonjour,

depuis quelques semaines je tente de m'initier à l'algorithmique avec le livre "Apprendre à programmer" pour ensuite apprendre le Python. Je coince sur un début d'algo de "recherche dichotomique itérative" et je me sens vraiment très bête. Voici le début de la méthode en question :

---

Bonjour,

une bonne démarche je pense :)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Classe VecteurEntier comporte methode rechercheDicho (x:entier): entier variables : gauche, milieu, droite : entier; trouve : booléen; Début gauche <--- 0; droite <--- taille-1; milieu <--- (gauche+droite)/2; trouve <--- Faux ;   tant-que ((gauche <ou= droite) ET (NON trouve)) faire ... etc..

---

Utilise les balise CODE quand tu insères du code, ce sera plus repérable et surtout plus lisible.

Citation:

---

Envoyé par sidonette

Je ne comprends pas la condition de la boucle "tant-que". Ca veut dire quoi "NON trouve"? A ce stade ça renvoie la valeur boléenne VRAI non? Mais alors la condition se traduit comme suit : "tant-que gauche < ou = droite et vrai, faire...". Pour moi ça n'a aucun sens! Quelqu'un saurait-il m'expliquer cette condition??

Merci beaucoup beaucoup!

Sidonie

---

L'exécution d'une instruction conditionnelle dépend de l'évaluation d'une condition, par exemple on ne rentre dans la boucle tant que que si la conditionnelle s'évalue à vrai.
Donc si on continue ton raisonnement à «ce stade» avec trouve qui vaut faux, gauche 0 et droite taille-1 (on supposera que taille>1) on obtient en remplaçant et en évaluant :

• tant que ( (gauche<=droite) et (non trouve) )
• tant que ( (0 <= taille-1) et (non faux) )
• tant que ( (vrai) et (vrai) )
• tant que (vrai) -> on rentre dans la boucle.

Il faut juste se souvenir des tables de vérités des operateurs booléems ou,et et non. Évidemment, ces variables vont voir leurs valeurs modifiées ce qui pourra faire changer la valeur de la conditionnelle du tant que à chaque tour de boucle (la conditionnelle est évaluée à chaque tour r de boucle).

Merci Souviron34 et Kwariz pour vos réponses et vos conseils. A l'avenir j'apprendrai à utiliser les balises code pour insérer du code.

Mais, Souviron 34, je ne suis pas certaine de comprendre l'explication que tu me donnes. J'ai fait des recherches sur ce qu'est un "flag" et j'ai beaucoup de mal à comprendre cette notion.

Comment sait-on que c'est un flag et qu'il doit être compris comme une expression et non une opération booléenne?? C'est un peu tordu ce truc de flag...

Merci de m'en expliquer davantage...

un "flag", ou un "drapeau", c'est un booléen..

Comme ici :

Code:

---

trouve <--- Faux ;

---

(en implémentation, on peut le faire comme un entier, ou uncaractère, si le type n'est pas défini, mais en algo, c'est stictement équivalent)..

Il n'admet que 2 valeurs : vrai ou faux, 0 ou 1

Quand on met l'expression ci-dessus, ça veut dire qu'on assigne "FAUX" au drapeau.

C'est tout..

Ok merci. C'est compris!!