[recherche sequentielle dans un tableau trié]

Version imprimable

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:

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

29/12/2005, 15h28
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).

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:

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:

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.

05/01/2006, 13h30
Laurent Gomila

Citation:

Code:

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.

Citation:

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

Citation:

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)".
05/01/2006, 13h49
diogene
Code:

1 2 while((i < h) && t[i] < cle_cherché)) {
donc h doit être la dimension du tableau (8 dans l'exemple)
Code:

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:

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

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

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.

05/01/2006, 14h23
Laurent Gomila

La position est i.

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