[recherche dichotomique dans un tableau trié]

**zui** · 05/01/2006, 15h50

J'ai ici un algo de recherche dichotomique que je voulais implementer en C++.

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
 
 PROCEDURE dicho (IN t:table, IN cle_cherchee : cles,
                              OUT reussi : logique, OUT milieu indices) Est
      VAR gauche, droite : indices;
      DEBUT
              gauche := Bas(t);
              droite := haut(t);
              reussi := Faux;
              TANTQUE NON reussi ET gauche < droite  BOUCLE
                   milieu := indices#Val((Ord(gauche)+Ord(droite)) Div 2);
                   SI cle_cherchee > cle(t[milieu])
                        ALORS gauche := Succ(milieu);
                   OUSI cle_cherchee <> cle(t[milieu])
                         ALORS droite := Pred(milieu)
                    SINON reussi := vrai
                    FIN SI
               FIN BOUCLE
FIN dicho;

J'ai une solution à proposer

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
 
void main(){
int t[8] = {1,4,8,12,15,22,25,30}; // tableau de 8 entiers
int gauche = 0; // une variable que j'initialise au bas du tableau
int droite = 7;  // une variable que j'initialise au haut du tableau
int milieu;
int cle_cherchee = 22 // l'element cherche est 22
( reussi := Faux) // je vois pas comment implementer cette instruction en C++
     While ((NON reussi) && (gauche < droite))  // Comment implementer aussi (NON reussi)????
       milieu = (gauche + droite) DIV 2;
       if (cle_cherchee > t[milieu])
           {
              gauche = milieu+1;
               else
                    if (cle_cherchee != t[milieu])
                        droite = milieu - 1;
                        else reussi = (t[milieu]==cle_cherchee)
            } // FIN SI
}  // FIN DU PROG

Vos corrections sont les biens venues. Merci.

**Laurent Gomila** · 05/01/2006, 16h01

Tu devrais plutôt consulter un cours de C++.

Les booléens c'est le type bool, pouvant prendre true ou false comme valeur.

Pour tester un booléen à faux c'est (b == false) ou (!b)

La division c'est /

**superspag** · 05/01/2006, 16h12

Je ne sais pas si l'algo est juste mais ça donnerai un truc comme ça :

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
void main() { 
 
  int t[8] = {1,4,8,12,15,22,25,30}; // tableau de 8 entiers 
  int gauche = 0; // une variable que j'initialise au bas du tableau 
  int droite = 7; // une variable que j'initialise au haut du tableau 
  int milieu; 
  int cle_cherchee = 22; // l'element cherche est 22 
 
  bool reussi = false;
 
  while( (! reussi) && (gauche < droite) ) {
    milieu = (gauche + droite) / 2; 
    if( cle_cherchee > t[milieu] ) { 
      gauche = milieu + 1; 
    } else if( cle_cherchee != t[milieu] ) {
      droite = milieu - 1; 
    } else {
      reussi = ( t[milieu] == cle_cherchee );
    } // FIN IF/ELSE 
  } // FIN WHILE
}  // FIN DU PROG

**zui** · 05/01/2006, 17h00

bool reussi = false;

Quand je compile le programme avec cette instruction, j'ai un message d'erreur : Undefined symbol 'bool'.

**superspag** · 05/01/2006, 17h09

Oula... tu es en C et pas en C++

Il faudrait deplacer ton post vers le bon forum

int reussi = 0; // pour Faux

et

while( (reussi == 0) && ...

**Elijha** · 05/01/2006, 20h13

Salut,

Effectivement, comme on te la dit, le type booléan n'existe pas en C, contrairement au Pascal.
Pour cela, en C, on définit la valeur 0 à l'état FAUX et la valeur 1 (ou différente de 0) à l'état VRAI.
Dans ton cas, tu peu définir un nouveau type (bool) avec 2 états TRUE ou FALSE.

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
typedef char bool ;  /* Le nouveau type booléan */
 
#define TRUE    1  /* TRUE sera remplacé par 1 */
#define FALSE   0  /* FALSE sera remplacé par 0 */
 
int main(void)
  {
  bool reussi = FALSE ;  /* Est équivalent à char reussi = 0 ; */
  .
  .
  reussi = TRUE ;  /* Est équivalent à reussi = 1 ; */
  .
  .
  /* Si reussi est égal à TRUE (donc 1) executer la condition */
  if(reussi==TRUE)
    {
    .
    .
    }
  .
  /* Si reussi est égal à FALSE (donc 0) executer la condition */
  if(reussi==FALSE)
    {
    .
    .
    }
  return 1 ;  /* Fin du programme */
  }

Maintenant, à toi de jouer

.

**PRomu@ld** · 05/01/2006, 20h19

Les booléens sont disponibles en incluant la librairie stdbool.h

**Emmanuel Delahaye** · 05/01/2006, 23h34

Envoyé par zui

J'ai ici un algo de recherche dichotomique que je voulais implementer en C++.

Et tu te dis comme ça :

"Tiens, ben je vais poster ça sur le forum C histoire de me faire bien voir..."

**Emmanuel Delahaye** · 05/01/2006, 23h34

Envoyé par PRomu@ld

Les booléens sont disponibles en incluant la librairie stdbool.h

En C99, uniquement...

**Elijha** · 05/01/2006, 23h53

Envoyé par Emmanuel Delahaye

Envoyé par PRomu@ld

Les booléens sont disponibles en incluant la librairie stdbool.h

En C99, uniquement...

Je ne comprenais pas, pourquoi je ne le trouvais pas dans mon répertoire include.

**PRomu@ld** · 06/01/2006, 06h37

Il faut vivre avec son temps messieurs ...

**Médinoc** · 06/01/2006, 11h10

Pas toujours facile d'avoir un compilo conforme au C99...
Les GCC de mon école datent (ils ne connaissent ni -std=c99 ni -Wextra) et même le dernier Visual n'y est pas conforme... (Surtout le dernier visual, en fait, grâce à sa géniale "bibliothèque run-time sécurisée"

)

En fait, y'a surtout les GCC récents qui sont plus ou moins conformes, comme celui fourni avec Dev-C++...

**Elijha** · 06/01/2006, 11h34

Salut,

Toujours sur les booléans : Existe-t'il un type booléen en C ?

Suffisait d'aller voir la faq

**PRomu@ld** · 06/01/2006, 17h38

Pas toujours facile d'avoir un compilo conforme au C99...

C'était une boutade !

Mais il est vrai que de temps en temps il est difficile d'avoir les dernières versions (pas forcément les toutes dernières mais quelque chose d'assez récent), surtout dans les domaines publics ...

**Emmanuel Delahaye** · 06/01/2006, 17h56

Envoyé par PRomu@ld

Mais il est vrai que de temps en temps il est difficile d'avoir les dernières versions (pas forcément les toutes dernières mais quelque chose d'assez récent), surtout dans les domaines publics ...

Je ne sais pas ce que tu appelles 'domaine public', mais à ma connaissance, GNU et FSF ne sont pas du domaine public...

On est gravement hors-sujet...

**PRomu@ld** · 06/01/2006, 18h00

Ah non, tu te méprend, je ne parlais pas de public dans ce sens, mais dans les établissement publics (genre éducation nationnale ...).

Désolé de ne pas avoir été plus clair ...

**Emmanuel Delahaye** · 06/01/2006, 18h42

Envoyé par PRomu@ld

Ah non, tu te méprend, je ne parlais pas de public dans ce sens, mais dans les établissement publics (genre éducation nationnale ...).

Désolé de ne pas avoir été plus clair ...

Etablissements et services publics. Ok.

Euh, connais pas. Je suis un mauvais français, et je ne connais que le privé!

**zui** · 09/01/2006, 00h14

Salut à tous,
J'ai fait un programme de recherche dichotomique en m'appuyant toutes les suggestions que vous avez données. Ca compile mais malheuresement je n'obtiens pas les résultats escomptés à l'execution du programme. Cad que quand je cherche un element qui ne se trouve pas dans la table exemple cle_cherchee = 99, j'obtiens "0" après l'execution du programme ce qui est tout à fait normal car ne se trouvant pas dans la table. Par contre que je cherche un element qui se trouve dans la table par exemple cle_cherchee = 4, j'obtiens toujours un "0" apres l'exécution du programme alors que je devrais obtenir un "1" pour dire que l'élément se trouve dans la table. Vos corrections sont les bien venues. Merci

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
 
#include <stdio.h>
 
void main(){
 
    int t[8] = {1,4,8,12,15,22,25,30};
    int gauche = 0;
    int droite = 7;
    int milieu;
    int reussi;
    int cle_cherchee = 4;
 
    while ((!reussi) && (gauche < droite)){
         milieu = (gauche + droite) / 2;
         if (che_cherchee > t[milieu])
            gauche = milieu + 1;
            else
            if (cle_cherchee != t[milieu])
               droite = milieu - 1;
               else
               reussi = (t[milieu]==cle_cherchee);
     }
}

**PRomu@ld** · 09/01/2006, 08h55

Pourquoi utilises-tu une variable reussi ? (de plus elle n'est pas initialiséee). Quand tu as trouvé ton élément, tu quittes.

De plus indente ton code correctement ça facilite la relecture (ton else n'est pas bien placé).

Si ça peut t'aider :

http://cermics.enpc.fr/polys/oap/node56.html

**Emmanuel Delahaye** · 09/01/2006, 09h19

Envoyé par zui

J'ai fait un programme de recherche dichotomique en m'appuyant toutes les suggestions que vous avez données. Ca compile

Hum, non !

Code :

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

1
2
3
4
5
6
7
8
9
 
Compiling: main.c
main.c:3: warning: function declaration isn't a prototype
main.c:3: warning: return type of 'main' is not `int'
main.c: In function `main':
main.c:14: error: `che_cherchee' undeclared (first use in this function)
main.c:14: error: (Each undeclared identifier is reported only once
main.c:14: error: for each function it appears in.)
Process terminated with status 1 (0 minutes, 7 seconds)

Merci de copier coller et non de retaper avec des fautes...

D'autre part :

http://emmanuel-delahaye.developpez....s.htm#typemain

[recherche dichotomique dans un tableau trié]

C

Discussions similaires

Partager

Partager