Discussion :

[remixtech]

Bonjour je dois faire une recherche dichotomique...

Donc j'ai fais un petit programme mais il ne fonctionne pas j'ai une violation d'accès je suis débutant, si vous pouviez m'expliquer ? de quoi il s'agit j'ai essayé de passer par les pointeurs rien à faire...

Vous avez une idée ?

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
#include <stdio.h>
#include <stdlib.h>
int i;
 
int recherche(int tableau[99],int index,int minimum,int maximum){
 int milieu;   
  milieu = ( maximum - minimum ) / 2;
    if (minimum==maximum)
                          if (index==tableau[milieu])
                          return index; 
                          else return 0;
 
 
                          else
                          {
                               if (tableau[milieu]<=index){
 
                                                           return recherche(tableau,index,minimum+1,milieu);
 
 
                                                           }
                                                           else
                                                           {
 
                                                           return recherche(tableau,index,milieu,maximum);   
 
                                                           }; 
 
 
                          };
 
 
}
 
 
int main(){
    int tableau[99];
    tableau[0] = 1;
    printf("%d",tableau[0]);
 
    for(i=1;i<=99;i++){
                       tableau[i] = tableau[i-1] + i ;
                      printf(" - %d",tableau[i]); }
    scanf("%d",i);
    printf("%d",recherche(tableau,10,0,99));                  
    scanf("%d",i);
 
}

merci

[fearyourself]

Quelques erreurs typiques:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
for(i=1;i<=99;i++)
  tableau[i] = ..

or ton tableau est défini avec int tableau[99]; , les indices vont donc de 0 à 98...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
scanf("%d",i);

est faux,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
scanf("%d",&i);

est juste mais scanf est déconseillé, voir les pages du forums pour une meilleure solution...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
milieu = ( maximum - minimum ) / 2;

n'est pas le milieu

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
milieu = ( maximum + minimum ) / 2;

l'est...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
if (index==tableau[milieu])
                          return index;
                          else return 0;

est une erreur puisque ton élément peut être à l'indice 0 (si tu cherches 1) par exemple, c'est le premier élément de ton tableau (pourquoi d'ailleurs?)

Ensuite, je ne vois pas pourquoi tu fais minimum+1 dans ton 1er appel récursif, rien ne prouve que l'élèment ne se trouve pas à tableau[minimum], tu ne l'as pas testé...

Jc

[ep31]

La condition d'arrêt de ta fonction récursive est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (minimum==maximum)

et à première vue, je dirai que ta fonction part en boucle infinie et tu dois avoir un stack overflow non ?

[remixtech]

Hargh ca ne fonctionne toujours pas !
En faite dev c++ démarre le programme et là il se ferme tout de suite...
Quand je debug des fois il me met access violation (segmentation fault)

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
#include <stdio.h>
#include <stdlib.h>
int i;
 
int recherche(int tableau[100],int index,int minimum,int maximum){
 int milieu;   
  milieu = ( maximum + minimum ) / 2;
    if (minimum==maximum)
                          if (index==tableau[milieu])
                          return index; 
                          else return -1;
 
 
                          else
                          {
                               if (tableau[milieu]<=index){
 
                                                           return recherche(tableau,index,minimum+1,milieu);
 
 
                                                           }
                                                           else
                                                           {
 
                                                           return recherche(tableau,index,milieu,maximum);   
 
                                                           }; 
 
 
                          };
 
 
}
 
 
int main(){
    int tableau[100];
    tableau[0] = 1;
    printf("%d",tableau[0]);
 
    for(i=1;i<=99;i++){
                       tableau[i] = tableau[i-1] + i ;
                      printf(" - %d",tableau[i]); }
 
    printf("%d",recherche(tableau,150,0,99));                  
    scanf("%d",&i);
 
}

Merci beaucoup pour vos réponses c'est sympa ,)

[diogene]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 if (tableau[milieu]<=index) 
       return recherche(tableau,index,minimum+1,milieu); 
 else  return recherche(tableau,index,milieu,maximum);

Apparemment, le test est inversé

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 if (tableau[milieu]>index) 
       return recherche(tableau,index,minimum+1,milieu); 
 else  return recherche(tableau,index,milieu,maximum);

La remarque de fearyourself est exacte au sujet de minimum+1.
Je crois que le code suivant devrait marcher :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
int recherche(int tableau[],int index,int minimum,int maximum)
{
  int milieu;
  if(tableau[minimum]==index) return minimum;
  if(tableau[maximum]==index) return maximum;
  if(tableau[minimum]>index || tableau[maximum]<index ) return -1;
  milieu = ( maximum + minimum ) / 2;
  if (tableau[milieu]>index)
        return recherche(tableau,index,minimum+1,milieu);
    else
        return recherche(tableau,index,milieu,maximum-1);
}