IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algo : recherche dichotomique itérative [Débutant(e)]


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Avril 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Avril 2009
    Messages : 5
    Points : 5
    Points
    5
    Par défaut 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

  2. #2
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par sidonette Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    "tant que ( (gauche <= droite) ET (trouve = faux) )
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  3. #3
    Membre expert
    Avatar de kwariz
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Octobre 2011
    Messages
    898
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Conseil

    Informations forums :
    Inscription : Octobre 2011
    Messages : 898
    Points : 3 352
    Points
    3 352
    Par défaut
    Citation Envoyé par sidonette Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 Voir le message
    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).

  4. #4
    Futur Membre du Club
    Profil pro
    Inscrit en
    Avril 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Avril 2009
    Messages : 5
    Points : 5
    Points
    5
    Par défaut
    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...

  5. #5
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    un "flag", ou un "drapeau", c'est un booléen..

    Comme ici :

    (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..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  6. #6
    Futur Membre du Club
    Profil pro
    Inscrit en
    Avril 2009
    Messages
    5
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Avril 2009
    Messages : 5
    Points : 5
    Points
    5
    Par défaut
    Ok merci. C'est compris!!

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algos recherche Opérationnelle
    Par cilia dans le forum Algorithmes et structures de données
    Réponses: 12
    Dernier message: 10/05/2006, 12h14
  2. recherche dichotomique sur chaînes de carctères
    Par contexte dans le forum Langage
    Réponses: 4
    Dernier message: 13/04/2006, 01h31
  3. Réponses: 23
    Dernier message: 10/01/2006, 14h33
  4. Recherche dichotomique
    Par remixtech dans le forum C
    Réponses: 4
    Dernier message: 06/01/2006, 19h39
  5. Recherche dichotomique
    Par Gryzzly dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 31/12/2005, 12h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo