1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2016
    Messages : 2
    Points : 3
    Points
    3

    Par défaut Recherche par dichotomie en C

    Bonjour,

    J'ai arpenté un peu le forum pour avoir une réponse à ma question mais je n'ai rien trouvé, ceci dit si mon topic n'a pas lieu d'être ou se trouve être un doublon signalez-le moi et je le supprimerai.

    Je cherche à faire un programme en C capable de générer un nombre aléatoire et de le trouver ensuite par une méthode de dichotomie. J'ai tourné comme j'ai pu ma boucle mais elle tourne à l'infini et je n'arrive pas à mettre le doigt sur le problème. J'ai rajouté au passage un compteur de tour pour savoir combien d'itérations ont été nécessaires au programme pour trouvé le bon nombre.
    Je ne sais pas si le problème est dans l'algorithme ou dans ma traduction en code.

    Je vous colle en dessous mon code :

    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
    23
    24
    25
    26
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
     
    int main(int argc, char *argv[])
    {
      int A = 1 , B = 100 , R = 2 , C = 0 , nombre = 0 , coup = 1; // A et B sont là pour définir où se trouve le nombre donné aléatoirement, C est là pour pouvoir avancer dans la dichotomie, nombre sera le nombre aléatoir et coup pour compter le nombre de boucles
      srand(time(NULL));
      nombre = (rand()% (B-A+1)) + A;
      printf("\n\n%d\n\n", nombre) ;
      printf("Trouvez le bon nombre entre 1 et 100\n") ;
      while(C != nombre)
      {
          coup++ ;
          C = (A+B)/2 ;
          printf("Proposition = %d\n" , C) ;
          if (C<nombre)
            printf("C'est plus !\n") ;
            B = C - 1;
          if (C>nombre)
            printf("c'est moins !\n") ;
            A = C + 1;
      }
      printf("\n\nGG, le bon nombre etait bien %d\nVous avez réussi en %d essais\n\n", C, coup);
      return 0;
    }

    Si quelqu'un est capable de me donner un piste ou même de déceler mon erreur je suis preneur !

    Merci beaucoup.

    B.

  2. #2
    Membre chevronné
    Avatar de Daïmanu
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2011
    Messages
    496
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2011
    Messages : 496
    Points : 1 765
    Points
    1 765

    Par défaut

    Bonjour, bienvenue sur le forum

    Je t'invite à mettre ton code dans la balise [ CODE ] pour plus de lisibilité (bouton # dans l'éditeur).

    Hormis les variables A, B et C qui mériteraient d'être appelées autrement, il est possible que ton soucis viennent du manque d'accolades autour des if. Sans accolades, seules la première instruction après le if est utilisée.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    if (C<nombre)
    printf("C'est plus !\n") ;
    B = C - 1;
    est équivalent à
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    if (C<nombre) {
        printf("C'est plus !\n") ;
    }
    B = C - 1;
    , or ce que tu veux c'est
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    if (C<nombre) {
        printf("C'est plus !\n") ;
        B = C - 1;
    }
    Je fais appel aux esprits de Ritchie, Kernighan, Stroustrup et Alexandrescu
    Donnez moi la force, donnez moi le courage de coder proprement !

    « Ça marche pas » n'est PAS une réponse convenable, merci de détailler le soucis en fournissant l’environnement, le code source, les commandes et les messages d'erreur.

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 926
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 5 926
    Points : 16 376
    Points
    16 376
    Billets dans le blog
    1

    Par défaut

    Bonjour

    Tu as à ta disposition un outil fabuleux: "printf". Tu aurais remplacé printf("Proposition = %d\n" , C) par printf("Proposition = %d (%d-%d)\n" , C, A, B) tu aurais trouvé de suite. Parce qu'en dehors des soucis d'accolades, tu as inversé les conséquences de l'évaluation.
    En effet, si C est trop petit, alors c'est que le nombre à trouver est placé après donc (au pire) entre C+1 et B.
    Et s'il est trop grand, alors c'est que le nombre à trouver est alors placé avant donc entre A et C-1.

    Or, dans le code
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    if (C<nombre)
        printf("C'est plus !\n") ;
        B = C - 1;
    if (C>nombre)
        printf("c'est moins !\n") ;
        A = C + 1;
    C'est écrit exactement le contraire...

    Accessoirement la formule nombre = (rand()% (B-A+1)) + A fonctionne (même avec ses parenthèses inutiles) mais n'offre pas un aléatoire vraiment uniforme (le modulo élimine toute une plage de valeurs potentiellement utilisables). Il vaut mieux utiliser la formule nombre = rand() / (double)RAND_MAX * (B-A+1) + A...

    PS: tu as mis "coup" à 1 et tu l'incrémentes en début de boucle => au premier essai il vaut déjà 2.
    PS2: ta variable "R" ? utile ?? pas utile ???
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Modérateur

    Avatar de Bktero
    Homme Profil pro
    Ingénieur systèmes embarqués
    Inscrit en
    juin 2009
    Messages
    3 582
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Ingénieur systèmes embarqués

    Informations forums :
    Inscription : juin 2009
    Messages : 3 582
    Points : 9 406
    Points
    9 406
    Billets dans le blog
    1

    Par défaut

    Bonjour,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    int A = 1 , B = 100 , R = 2 , C = 0 , nombre = 0 , coup = 1; // A et B sont là pour définir où se trouve le nombre donné aléatoirement, C est là pour pouvoir avancer dans la dichotomie, nombre sera le nombre aléatoir et coup pour compter le nombre de boucles
    Très bon commentaire mais comme l'a dit Daïmanu, il vaut mieux donner des noms explicites à tes variables pour que le commentaire ne soit plus utile.
    Exemple :
    • A -> borneInferieure
    • C --> valeurCourante


    Compléter le commentaire de Sve@r sur rand(), voir la FAQ https://c.developpez.com/faq/?page=L...res-aleatoires

  5. #5
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Arts - Culture

    Informations forums :
    Inscription : octobre 2016
    Messages : 2
    Points : 3
    Points
    3

    Par défaut

    Bonjour,

    Merci beaucoup pour vos réponses !

    Déjà merci d'avoir rajouté les balises codes. Ensuite, en prenant en compte vos remarques mon programme a fini par fonctionner.

    Merci aussi de m'avoir indiqué des réflexes à adopter pour déceler mes erreurs et rendre mon code plus lisible.

    B.

Discussions similaires

  1. [HFSQLCS]optimiser la vitesse de recherche par dichotomie ?
    Par courdi95 dans le forum HyperFileSQL
    Réponses: 9
    Dernier message: 03/12/2012, 11h46
  2. recherche par mot clé
    Par seb59dk dans le forum Access
    Réponses: 3
    Dernier message: 06/09/2005, 15h26
  3. Recherche par mots clés
    Par legillou dans le forum Général Algorithmique
    Réponses: 4
    Dernier message: 17/06/2005, 11h56
  4. Probleme de recherche par listbox
    Par haigwepa dans le forum IHM
    Réponses: 6
    Dernier message: 12/10/2004, 20h57
  5. Moteur de recherche par date
    Par Prue dans le forum ASP
    Réponses: 17
    Dernier message: 27/08/2003, 17h07

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