1. #1
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 20
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2017
    Messages : 3
    Points : 0
    Points
    0

    Par défaut Algorithme de recherche dichotomique récursive

    Bonjour à tous je débute en informatique et je voulais faire un algorithme qui permet de faire une recherche dichotomique dans un tableau avec la récursivité.
    J'ai un problème dans mon code que je n'arrive pas à résoudre, quand je l’exécute il me dit qu'il y a une erreur de segmentation..
    Pourriez vous m'aider à trouver ce qui ne va pas s'il vous plaît ? :/

    Voilà mon code

    Code C : 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
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <time.h>
     
    #define N 30
     
    /* Fonction de comparaison de 2 entiers, utilisée par qsort */
    int comp (const void * a, const void * b)
    {
        return ( *((int*)a) - *((int*)b) );
    }
     
    /* Fonction d'affichage d'un tableau */
    void afficheTableau(int t[], int size)
    {
        int i;
        for (i=0; i < size; ++i)
            printf("%d ", t[i]);
        printf("\n");
    }
     
    bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
     int milieu = (indexR+indexL)/2;
         if(elem == tab[milieu]) 
            return true;
         else
         {
            if (elem < tab[milieu]){ 
                  rechercheDichotomique(tab,elem, indexL, milieu-1);}
            if (elem>tab[milieu]){
                  rechercheDichotomique(tab,elem, milieu+1, indexR);}
         }
     
         return false;
    }
     
     
    int main() {
        int tab[N];
        int elem1, elem2;
        int i;
     
        //generation aleatoire des elements du tableau
        srand(time(NULL));
        for(i = 0; i < N; ++i) {
            tab[i] = rand()%100;
        }
     
        //tri du tableau
        qsort (tab, N, sizeof(int), comp);
     
        elem1 = tab[N-1];
        elem2 = 100;
     
        printf("Le tableau tab: \n");
        afficheTableau(tab, N);
     
     
        printf("Element à rechercher:");
        int elem;
        scanf("%d", &elem);
        int indexR = elem2;
        int indexL = elem1;
        rechercheDichotomique(tab,elem,indexL,indexR);
     
     
        return EXIT_SUCCESS;
    }

  2. #2
    Membre chevronné
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    446
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 446
    Points : 1 951
    Points
    1 951

    Par défaut

    Bonjour,

    Il y a une erreur algorithmique dans rechercheDichotomique : l'instruction return false; n'est jamais atteignable.
    Si tu recherches un élément qui n'existe pas dans le tableau, tu as une récursivité infinie.

  3. #3
    Membre émérite
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    décembre 2015
    Messages
    548
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2015
    Messages : 548
    Points : 2 856
    Points
    2 856

    Par défaut

    Bonjour,
    Il y a plusieurs problèmes:
    Dans l'appel principal à rechercheDichotomique les 2 derniers paramètres doivent être des index, pas les valeurs que l'on trouve à ces index. Donc bool trouve = rechercheDichotomique(tab,elem,0,N);. Et ça serait peut-être intéressant d'afficher si l'élément à été trouvé!

    Dans la fonction elle-même, il manque des cas à contrôler. Si la valeur n'existe pas dans le tableau, il risque de se passer n'importe quoi.
    Par exemple si plus grand et milieu>=indexR ou bien si plus petit et milieu<indexL, c'est que la recherche a échoué, et il ne faut pas appeler la fonction récursivement, c'est là qu'il faut retourner false. Dans les autres cas on doit retourner ce que retourne l'appel récursif.

  4. #4
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 20
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2017
    Messages : 3
    Points : 0
    Points
    0

    Par défaut

    J'ai essayé de corrigé ça, j'ai rajouté les différents cas quand l’élément n'est pas dans le tableau et si j'essaye de lancer le programme et de rechercher un élément qui n'est pas dans le tableau, il y a une erreur de segmentation
    J'ai rajouté les cas:

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    if(milieu>indexR || milieu<indexL){
             return false;
         }
         if((elem>indexR) || (elem<indexL)){
             return false;
         }

  5. #5
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 846
    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 846
    Points : 16 117
    Points
    16 117
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Saemina Voir le message
    J'ai essayé de corrigé ça, j'ai rajouté les différents cas quand l’élément n'est pas dans le tableau et si j'essaye de lancer le programme et de rechercher un élément qui n'est pas dans le tableau, il y a une erreur de segmentation
    J'ai rajouté les cas:

    if(milieu>indexR || milieu<indexL){
    return false;
    }
    if((elem>indexR) || (elem<indexL)){
    return false;
    }
    Bonjour

    Ce n'est pas que ça qu'il faut faire.
    Quand tu appelles ta recherche récursive sur une sous-partie du tableau (gauche/droite), il te faut d'une façon ou d'une autre renvoyer son résultat à l'appelant (qui étant la même fonction récupère alors ce résultat et le renvoie à l'appelant et etc.). Parce que là, tu appelles ta fonction et tu ne fais rien de ce qu'elle te retourne...

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
        int milieu = (indexR+indexL)/2;
     
        if(elem == tab[milieu]) return true;
        if (indexL == indexR) return false;
     
        if (elem < tab[milieu]) return rechercheDichotomique(tab,elem, indexL, milieu - 1);
        else return rechercheDichotomique(tab,elem, milieu + 1, indexR);
    }

    Après, évidemment, il faut l'appeler dans le main avec les bons paramètres parce que j'ai rien compris à tes calculs (c'est quoi ce "100" à la con qui arrive d'on ne sait où ??? c'est sûr que si le tableau n'a que 30 cases, il va pas trop aimer que tu lui demandes de chercher dans les 70 suivantes...)... et aussi afficher son résultat !!!
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    	printf("Element à rechercher:");
    	int elem;
    	scanf("%d", &elem);
    	printf("%d\n", rechercheDichotomique(tab, elem, 0, N));

    Ensuite (optimisation), tu transformes ta fonction en int et tu lui fais renvoyer "milieu" si elle trouve ou "-1" si elle ne trouve pas. Ainsi, au lieu d'avoir une bête fonction à qui tu demandes "pouvez-vous me le trouver" et qui te répond "oui je le peux", t'as une bath fonction à qui tu demandes "pouvez-vous me le trouver" et qui te répond "il est là"...
    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

  6. #6
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    octobre 2017
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 20
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : octobre 2017
    Messages : 3
    Points : 0
    Points
    0

    Par défaut

    J'ai corrigé ma fonction mais elle m'affiche tout le temps 1 alors que le nombre n'est pas présent dans le tableau..

    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
    bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
        int milieu =(indexL+indexR)/2;
        if (indexL > indexR)
            return -1;
     
       if (elem == tab[milieu])
            return true;
     
        if (elem < tab[milieu])
            return rechercheDichotomique(tab, indexL, milieu-1, elem);
     
        else 
            return rechercheDichotomique(tab, milieu+1, indexR, elem);
     
    }
    Pour tester la fonction:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    	printf("Element à rechercher:%d\n",elem2);
    	printf("%d\n", rechercheDichotomique(tab, elem2, 0, elem1));

  7. #7
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 846
    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 846
    Points : 16 117
    Points
    16 117
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Saemina Voir le message
    J'ai corrigé ma fonction mais elle m'affiche tout le temps 1 alors que le nombre n'est pas présent dans le tableau..

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool rechercheDichotomique (int tab[], int elem, int indexL, int indexR){
        int milieu =(indexL+indexR)/2;
        if (indexL > indexR)
            return -1;
     
       if (elem == tab[milieu])
            return true;
     
        if (elem < tab[milieu])
            return rechercheDichotomique(tab, indexL, milieu-1, elem);
     
        else 
            return rechercheDichotomique(tab, milieu+1, indexR, elem);
     
    }

    Pour tester la fonction:

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    	printf("Element à rechercher:%d\n",elem2);
    	printf("%d\n", rechercheDichotomique(tab, elem2, 0, elem1));


    Que veux-tu qu'on te dise ??? Si tu fais retourner -1 via une fonction de type "bool" ben comme c'est différent de 0 le booléen est vrai et un vrai affiché au format "%d" donne 1.
    Faut que t'arrêtes de faire le bébé et que tu te sortes un peu les doigts quoi. T'as un cerveau, c'est déjà pour t'en servir un minimum en apprenant les bases avant de solliciter les notres.

    Accessoirement ta fonction est prévue pour recevoir le tableau, l'élément à chercher, l'index min et l'index max. Tout ça dans cet ordre strict.
    Dans le main tu lui passes le tableau, elem2 (on va dire admettre que c'est l'élément à chercher), 0 (on dira que c'est l'index min, ça colle) et elem1. T'es sûr que elem1 est l'index max ???
    Ensuite dans la récursion, là tu lui passes le tableau, puis tes index, puis l'élément à rechercher. Bref après le tableau rien d'autre dans le bon ordre. Je t'ai pourtant écrit une fonction correcte et sa façon de s'en servir. Tu aurais-pu au-moins t'en inspirer !!!
    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

Discussions similaires

  1. Recherche dichotomique récursive
    Par bj303931 dans le forum Général Java
    Réponses: 1
    Dernier message: 25/01/2017, 15h48
  2. [Free Pascal] Fonction récursive de recherche dichotomique
    Par fleurose dans le forum Free Pascal
    Réponses: 4
    Dernier message: 13/04/2011, 19h55
  3. [Débutant] Recherche dichotomique récursive
    Par kenon69 dans le forum Assembleur
    Réponses: 7
    Dernier message: 13/10/2008, 23h51
  4. Algorithme de recherche de chemin
    Par amelie gaya dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 09/06/2002, 15h29

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