Problème fonction recherche

Version imprimable

Bonjour,

j'ai un petit problème avec un exercice sur les fonctions:

ce que je cherche à faire:

écrire la fonction (rechdicho) qui détermine si une valeur donnée appartient à un tableau donné à une dimension d’entiers. Le tableau est supposé trié. Si la valeur se trouve dans le tableau, la fonction renvoie sa position

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
 
 
#include <stdio.h>
#include <stdlib.h>
 
#define TAILLE_TAB 10
 
/*
 * 
 */
void rechdicho(int val, int *tab, int taille){
    int compteur, pos;
 
    if (val == tab[taille/2]) {
        pos = taille/2;       
    }
    else if (val < tab[taille/2]) {
        for (compteur=0; compteur <= taille/2; compteur++){
            if (val == tab[compteur]){
                pos = compteur;
            }                     
        }           
    }
    else {
        for (compteur=taille/2; compteur <= taille-1; compteur++){
            if (val == tab[compteur]){
                pos = compteur;
            }                     
        }           
    }         
    return (pos);
} 
 
int main(int argc, char** argv) {
    int position;
    int tableau[TAILLE_TAB] = {1,3,5,6,7,8,9,11,44,55};
    int val;
    char MSG_USERS1[255] = "Encodez une valeur: ";
    char MSG_USERS2[255] = "La position de votre valeur dans le tableau est: ";
 
    printf ("%s",MSG_USERS1);
    scanf ("%d", &val);
 
    position = rechdicho(val, tableau, TAILLE_TAB);
    printf ("%s",MSG_USERS1);
    printf ("%d", position);
 
}

27/03/2014, 08h27
Trademark
Salut,

Ton algo n'est pas une recherche dichotomique vu qu'il ne coupe le tableau en deux qu'une fois, il faut que tu coupes le tableau en deux jusqu'à ce que tu trouves la valeur. Pour ce faire, je te conseille d'utiliser 3 variables supplémentaires : int debut, fin, milieu; et de réfléchir avec ces variables :-)

Sinon qql remarques générales sur ton code :
1. char MSG_USERS1[255] pourquoi 255 ? Utilise char* MSG_ASK_VALUE = ...
2. Comme tu vois j'ai également changé le nom, il faut être explicite et éviter de numéroter les noms.
3. return (pos);, tu peux te passer des parenthèses.
27/03/2014, 13h57
Ersch
Hello et merci pour ton aide, je vais regarder pour modifier mon algorithme avec tes conseils, cependant j'ai encore un problème car quand j'appelle ma fonction netbeans me donne une erreur:
Code:

1 2 main.c:49:14: error: void value not ignored as it ought to be position = rechdicho(val, tableau, TAILLE_TAB);
27/03/2014, 14h21
dahtah
Citation:
Envoyé par Ersch

Code:

1 2 main.c:49:14: error: void value not ignored as it ought to be position = rechdicho(val, tableau, TAILLE_TAB);
Ta fonction rechdicho() est declaree comme ne retournant rien:

Code:

void rechdicho(int val, int *tab, int taille);

Tu ne peux donc pas affecter une valeur de retour. Si tu veux recuperer une valeur de retour, tu dois modifier le prototype en:

Code:

unsigned int rechdicho(int val, int *tab, int taille);

unsigned parce qu'une postion n'est pas censee etre negative ;)

Les parametres de ta fonction ne sont pas modifies pas la fonction elle meme. Tu peux donc les declares const.
27/03/2014, 16h07
gerald3d

La fonction rechdicho(int val, int *tab, int taille); pourrait aussi renvoyer un entier signé. Ainsi si le retour est négatif le nombre n'a pas était trouvé dans le tableau. Ce n'est qu'une remarque de style bien sûr.
28/03/2014, 10h01
Médinoc

C'est même ce que font certaines bibliothèques, retournant le complément à 2* de l'index où l'on devrait insérer la valeur si elle n'est pas là.

*C'est-à-dire, -index-1 ou -(index+1); c'est nécessaire pour traiter le cas d'une insertion à l'index zéro.

Merci à tous pour vos remarques, voila mon nouveau 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
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h>
 
#define TAILLE_TAB 10
 
/*
 * 
 */
unsigned int rechdicho(int val, int *tab, int taille){
 
int imin = 0;
int imax = taille;
int imilieu;
int irecherche;
 
 
while ((imin <= imax) && (tab[imilieu] != val)){
imilieu = (imin+imax)/2;
 
    if (tab[imilieu] == val) {
        irecherche = imilieu;
    }
        else {
 
        }if (tab[imilieu] > val){
                imax = imilieu-1;
        }else
        {
            imin = imilieu+1;
        }  
}
 
return irecherche;
 
} 
 
int main(int argc, char** argv) {
    int position;
    int tableau[TAILLE_TAB] = {1,3,5,6,7,8,9,11,44,55};
    int val;
    char MSG_USERS1[255] = "Encodez une valeur: ";
    char MSG_USERS2[255] = "La position de votre valeur dans le tableau est: ";
 
    printf ("%s",MSG_USERS1);
    scanf ("%d", &val);
 
    position = rechdicho(val, tableau, TAILLE_TAB);
    printf ("%s",MSG_USERS2);
    printf ("%d", position);
 
}

01/04/2014, 08h22
Bktero

Citation:

Envoyé par dahtah

Code:

unsigned int rechdicho(int val, int *tab, int taille);

unsigned parce qu'une postion n'est pas censee etre negative ;)

Le type size_t est fait pour cela ;)