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

 C Discussion :

la dichotomie recursive


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Femme Profil pro
    Développeur Java
    Inscrit en
    Juillet 2010
    Messages
    48
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Juillet 2010
    Messages : 48
    Par défaut la dichotomie recursive
    Salu tout le monde,svp jaimeriais bien que que vous maidiez a propos dun petit programme qui consite a chercher une valeur dans un tableau dune facon dichotomqie
    voila 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
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <stdio.h>
    #include <stdlib.h>
     
    int chercher(int t[],int debut,int fin,int valeur)
    {
        int milieu;
        milieu=(debut+fin)/2;
        if(valeur==t[milieu])
        {
            printf("la valeur se trouve a la position %d",milieu);
        }
        else if(valeur<t[milieu])
        {
            return chercher(t,debut,milieu-1,valeur);
        }
        else if(valeur>t[milieu])
        {
            return chercher(t,milieu+1,fin,valeur);
        }
        else
        {
            printf("po de valeur");
        }
    }
     
     
     
     
         main()
         {
             int val;
             int t[5]={2,3,5,7,98};
             int debut=0;
              int nouveau=4;
             printf("entrez");
             scanf("%d",&val);
           chercher(t,debut,nouveau,val);
             return 0;
         }
    le problem c que quand jentre une valeur qui existe dans le tableau ca marche mais sinon ca ne marche pas et ca plante quand la valeur nexiste po

  2. #2
    Membre Expert
    Profil pro
    Développeur en systèmes embarqués retraité
    Inscrit en
    Mars 2006
    Messages
    952
    Détails du profil
    Informations personnelles :
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Mars 2006
    Messages : 952
    Par défaut
    Salut,

    Je t'encourage a utiliser un debogueur, ça m'a trouvé l'erreur en 30 secondes. Au bout d'un moment, en cherchant la valeur 97, debut vaut 4 et fin vaut 3. ces valeurs ne bougent plus et c'est la récursivité de la fonction qui provoque le plantage.

    A+

    Pfeuh

    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
    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
    #include <stdio.h>
     
    #define VALEUR_NON_TROUVEE -1
     
    int chercher(int t[], int debut, int fin, int valeur)
    {
        int milieu;
     
        if (valeur < t[debut])
        {
            return VALEUR_NON_TROUVEE;
        }
        if (valeur > t[fin])
        {
            return VALEUR_NON_TROUVEE;
        }
        if (valeur == t[debut])
        {
            return debut;
        }
        if (valeur == t[fin])
        {
            return fin;
        }
        else
        {
            milieu = (debut + fin) / 2;
            if (milieu == debut)
            {
                return VALEUR_NON_TROUVEE;
            }
            if (valeur < t[milieu])
            {
                return chercher(t, debut, milieu, valeur);
            }
            else
            {
                return chercher(t, milieu, fin, valeur);
            }
        }
    }
     
    int main(void)
    {
        int val;
        int t[] = {2, 3, 5, 7, 98};
        int position;
     
        printf("entrez la valeur a rechercher:");
        scanf("%d",&val);
        position = chercher(t, 0, sizeof t / sizeof(int), val);
        if(position != VALEUR_NON_TROUVEE)
            printf ("la valeur %i est a la position %i", val, position);
        else
            printf ("la valeur %i n'a pas ete trouvee", val);
        return 0;
    }

  3. #3
    Membre averti
    Femme Profil pro
    Développeur Java
    Inscrit en
    Juillet 2010
    Messages
    48
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Juillet 2010
    Messages : 48
    Par défaut
    essaie de recompiler ton code avec une valeur qui existe ....ca donne toujours le meme message" la valeur recherchée n'existe pas")meme si la valeur existe

  4. #4
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Chercheur d'emploi
    Inscrit en
    Septembre 2007
    Messages
    7 477
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur d'emploi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 477
    Par défaut
    Citation Envoyé par Cyang Voir le message
    le problem c que quand jentre une valeur qui existe dans le tableau ca marche mais sinon ca ne marche pas et ca plante quand la valeur nexiste po
    C'est normal ! Regarde ton code :




    Citation Envoyé par Cyang 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
    #include <stdio.h>
    #include <stdlib.h>
     
    int chercher(int t[],int debut,int fin,int valeur)
    {
        if(valeur==t[milieu])
        else if(valeur<t[milieu])
        else if(valeur>t[milieu])
        else
        {
            printf("po de valeur");
        }
    }
    Le dernier cas de figure n'est JAMAIS atteint : une valeur entière que tu arrives à lire ne peut pas être ni égale, ni supérieure ni inférieure à la valeur de comparaison (à moins que tu ne te réfères à certains langages de plus haut niveau dans lequels les entiers sont des objets et les symboles qui les désignent, des références éventuellement NULL, ce qui n'existe pas en C).

    Le seul moyen valable de conclure à la non-existence d'une valeur dans ton tableau est de vérifier si « début == fin », auquel cas il n'y a plus lieu de diviser en deux parties le singleton restant, chose que tu ne fais manifestement pas. Et ça c'est un problème parce que (0+0) ÷ 2 - 1 = -1. Tu te retrouves alors avec {début=0; fin=-1}. Ça veut dire que tu rencontre la fin avant l'arrivée, d'une part, et que tes indices sont en dehors du tableau. Converti en entier non signé, ton entier vaut 0xFFFFFFFF, soit des kilomètres au delà de ton segment de mémoire. Ça se termine invariablement en segfault.

  5. #5
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 967
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 967
    Par défaut
    Hia,

    D'autre part, utiliser la récursivité pour la recherche dichotomique est plutôt aberrant côté algorithmique.

Discussions similaires

  1. [COMPILATION][RECURSIVE] outil ?
    Par narmataru dans le forum Build
    Réponses: 6
    Dernier message: 14/01/2009, 15h05
  2. WITH RECURSIVE
    Par Médiat dans le forum Décisions SGBD
    Réponses: 3
    Dernier message: 16/06/2005, 09h17
  3. problème avec une procédure recursive
    Par vbcasimir dans le forum SQL
    Réponses: 1
    Dernier message: 10/06/2005, 16h38
  4. [C++] Creer des repertoires de facon recursive
    Par barthelv dans le forum Windows
    Réponses: 2
    Dernier message: 25/04/2005, 15h12
  5. Exploitation d'une table possédant une relation recursive
    Par VincentR dans le forum Langage SQL
    Réponses: 2
    Dernier message: 26/08/2004, 11h07

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