Discussion :

[zui]

Bonjour à tous.
Je suis entrain d'apprendre les programmes de tri en C.
J'ai ici "un algorithme de recherche séquentielle dans un tableau trié" que je voulais exécuter sous C++ de borland.

" Supposons la table triée en ordre croissant. On arrêtera la recherche dès qu'on trouve l'élément ou un élément dont la clé est supérieure à la clé cherchée. On suppose aussi que l'élément cherché se trouve dans la table :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
    PROCEDURE rech_seq_triee(IN  t:table,
                                             IN  cle_cherchee : cles,
                                             out  reussi : logique,
                                             out  i : indices)  EST
        var h  :  indices;
        DEBUT
            h  :=  Haut(t);  i  :=  Bas(t);
            TANTQUE  i<h  ET  cle(t[i] <  cle_cherchee  BOUCLE
                 i := succ(i);
            FIN BOUCLE;
            reussi :=  cle(t[i]) = cle_cherchee
       FIN rech_seq_triee;

/*NB : petit commentaire de ma part.
i veut dire le premier element du tableau.
h veut dire le dernier element du tableau.
i := succ(i) veut dire "i++" mais je ne suis pas sur
A mon avis il faut partir d'un exemple de tableau. Vous pouvez utilser vos propres variables. */

Merci à tous. Vos solutions sont les bien venues

[Laurent Gomila]

On n'est pas là pour faire les devoirs des étudiants.

Montre nous ce que tu as déjà fait, et explique nous en détail sur quoi tu bloques exactement.

De plus si tu dois le faire en C alors tu es sur le mauvais forum (si c'est le cas il faudra demander à faire déplacer ton post).

[zui]

Je souhaite d'abord à tous les membres mes meilleurs voeux pour 2006.
C'est pas un devoir mais c'est juste une revision pour les examens.
Je vais proposer ma solution:

Supposons que l'on a une table triée [ 1| 4| 8| 12| 15| 22| 25| 30]. Le but c'est de chercher un élément dans la table, dire à quelle position on l'a trouvé. L'algo est le suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
PROCEDURE rech_seq_triee(IN t:table, 
                   IN cle_cherchee : cles, 
                   out reussi : logique, 
                   out i : indices) EST 
                   var h : indices; 
DEBUT 
    h := Haut(t); i := Bas(t); 
     TANTQUE i<h ET cle(t[i] < cle_cherchee BOUCLE 
        i := succ(i); 
     FIN BOUCLE; 
     reussi := cle(t[i]) = cle_cherchee 
FIN rech_seq_triee;

Son implémentation en C++ est le suivant :

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
 
void main(){
 
int t[8] = {1,4,8,12,15,22,25,30};   // declaration d'un tableau de 8 élements, que j'ai initialisé en meme temps
int i = 0;   //declaration d'un entier que je initialise à la position du premier élément du tableau
int h = 9;  //declaration d'un entier que j'initialise à la position du dernier element du tableau
 
/* Je vais boucler. Je rappelle que la condtion d'arret de la boucle est : On arrêtera la recherche dès qu'on trouve l'élément ou un élément dont la clé est supérieure à la clé cherchée*/
 
/* Voila mon probleme : je ne sais pas comment exprimer " cle_cherché " en C++. Supposons qu'on cherche "22" dans le tableau, comment ecrire la condition pour que le programme s'arrete une fois qu'il aura rencontré " 22" ???
 
while((i < h) && t[i] < cle_cherché)) 
{
i++; // j'incrémente i
}  // fin de la boucle
reussi = t[i]; // reussi donne la position où l'on trouve le nombre cherché
} // fin du programme principale.

C'est ca ce que je crois etre une partie de la solution. Vos contributions sont les bien venues.

[Laurent Gomila]

Code :

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

int h = 9;  //declaration d'un entier que j'initialise à la position du dernier element du tableau

h devrait valoir 7, ton tableau comportant 8 éléments.

Voila mon probleme : je ne sais pas comment exprimer " cle_cherché " en C++. Supposons qu'on cherche "22" dans le tableau, comment ecrire la condition pour que le programme s'arrete une fois qu'il aura rencontré " 22" ???

"int cle_cherchee = 22;" :

reussi = t[i]; // reussi donne la position où l'on trouve le nombre cherché

D'après ton algorithme, reussi doit valoir vrai si tu as trouvé l'élément, faux sinon. Donc ce serait plutôt "reussi = (t[i] == cle_cherchee)".

[diogene]

Code :

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

1
2
while((i < h) && t[i] < cle_cherché)) 
{

donc h doit être la dimension du tableau (8 dans l'exemple)

Code :

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

1
2
3
i++; // j'incrémente i 
}  // fin de la boucle 
reussi = t[i]; // reussi donne la position où l'on trouve le nombre cherché

On peut sortir du while soit après avoir trouvé ou dépassé cle_cherche, alors i<h et t[i] est correct, soit parce que i>=h alors t[i] est hors du tableau et le programme plante

Code :

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

reussi = i<h && t[i] ==cle_cherche;

Accessoirement, le commentaire associé à cette dernière ligne est faux. Il vaut mieux ne pas mettre de commentaires que des commentaires faux

[zui]

Merci, vous etes genial. Ca marche très bien. Vous avez raison h=7. Voila le code que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void main(){
 
int t[8] = {1,4,8,12,15,22,25,30};
int i = 0;
int h = 7;
int reussi;
int cle_cherchee = 22;
 
while ((i < h) && (t[i] < cle_cherchee))
     i++;
reussi = (t[i]==cle_cherchee);
printf("%d", reussi);
}

Ca tres bien marché. Supposons qu'on nous demande de dire la position à laquelle on a trouve "22", quelle instruction faudrait ajouter au programme? Merci.

[Laurent Gomila]

La position est i.

diogene : en mettant h à 7 et non à 8, il n'y a aucun problème de borne.