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 :

Invariant de boucle


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 39
    Points : 38
    Points
    38
    Par défaut Invariant de boucle
    Bonjour,
    Quelqu’un pourrait-il me donner un invariant de boucle de l’algorithme de recherche dichotomique s’il vous plaît?
    Merci

  2. #2
    Membre confirmé
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    139
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 139
    Points : 531
    Points
    531
    Par défaut
    On part du code qui requiert un tableau array trié et qui renvoie soit l'indice dans array de la valeur cherchée si array la contient, -1 sinon :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    dsearch( value, array )
    begin
        found = false
        left = 0
        right = array.length-1
        while not found and left<=right do
            median = (left+right) div 2
     
            if array[median]==value then
                value = true
            else
                if array[median]<value then
                    left = median + 1
                else
                    right = median - 1
                end if
            end if
     
        end while
     
        return found?median:-1
    end
    Dans ce code je t'ai écrit la conditionnelle sous une forme un peu explosée, mais elle te permet de trouver facilement un invariant de boucle de la forme «soit la valeur est trouvée et found est vrai, soit on réduit l'intervalle du tableau susceptible de contenir value par rapport à l'itération précédente.»

  3. #3
    Nouveau membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 39
    Points : 38
    Points
    38
    Par défaut
    Merci beaucoup!

  4. #4
    Membre expérimenté

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 425
    Points : 1 356
    Points
    1 356
    Par défaut Modification
    Bonjour WhiteCrow,

    Je crois que la ligne 10 : value = true devrait être found = true.
    Citation Envoyé par WhiteCrow Voir le message
    ...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    dsearch( value, array )
    begin
        found = false
        left = 0
        right = array.length-1
        while not found and left<=right do
            median = (left+right) div 2
     
            if array[median]==value then
                value = true
            else
                if array[median]<value then
                    left = median + 1
                else
                    right = median - 1
                end if
            end if
     
        end while
     
        return found?median:-1
    end
    ...
    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  5. #5
    Membre confirmé
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    139
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 139
    Points : 531
    Points
    531
    Par défaut
    Merci !
    Je corrige le message en conséquence.

    Edit:
    Malheureusement le message est trop ancien pour la correction. Je la publie donc ici:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    dsearch( value, array )
    begin
        found = false
        left = 0
        right = array.length-1
        while not found and left<=right do
            median = (left+right) div 2
     
            if array[median]==value then
                found = true
            else
                if array[median]<value then
                    left = median + 1
                else
                    right = median - 1
                end if
            end if
     
        end while
     
        return found?median:-1
    end

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

Discussions similaires

  1. Démontrer qu'un algorithme se termine par des invariants de boucle
    Par Pouknouki dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 18/02/2016, 00h54
  2. Invariant de boucle entrée/sortie
    Par martin999999 dans le forum Caml
    Réponses: 9
    Dernier message: 24/09/2012, 00h07
  3. Invariant de boucle
    Par pomme_verte dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 11/03/2012, 19h04
  4. Invariant de boucle
    Par larchicha dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 17/11/2011, 12h02
  5. Calcul d'un invariant de boucle
    Par caroline-bx1 dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 21/10/2011, 14h03

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