la dichotomie recursive

Version imprimable

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:

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:?

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:

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;
}

27/09/2010, 15h40
Cyang

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 :roll:

Citation:

Envoyé par Cyang

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
Code:

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.

27/09/2010, 17h27
droggo

Hia,

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