Cours Asd Prepa1

Algorithme de recherche séquentielle
Représentation informelle :
Soit un tableau a et une information à rechercher dans ce
tableau. L’algorithme de recherche séquentielle (ou linéaire)
consiste à regarder successivement en partant du 1er élément
de a, est ce que cet élément coïncide avec info ?
Réalisation en C :
Soit un annuaire téléphonique formé de pairs<nom.tel> on
souhaite connaitre le numéro de téléphone d’un abonné
donné.
L’algorithme de recherche séquentielle modélise un problème

de recherche avec 2 issus positifs ou négatifs --> on opte pour
une fonction
GRAIET & HAMEL 2020 124

#include<stdio.h>
#include<string,h> asma abbasi aissao ons benam ben
#define n 100 122 125 12 23 2 78
char* nom[n] ;
int tel [n] ; /*info=« abbassi »
int recherche_seq (char * info) /*rend (-1) si info n’appartient pas à nom
sinon elle retourne Le téléphone correspondant*/
{
unsigned i ; /*pour parcourir*/
for(i=0 ;i<n ;i++)
if (strcmp(nom[i],info)==0)
return tel[i] ;
return -1 ; }
strcmp
• strcmp(chaine 1, chaine2)= 0 si chaine1
est égale à chaine2
• strcmp(chaine1, chaine2)=1 si chaine 1>
chaine2
• Strcmp(chaine 1, chaine2)= - 1 si chaine
1<chaine2
• Ahmed> Ahmedia
• Ahmed =Ahmed
• ahmad>ahmed
Recherche d’une table :
 Inconvénient : On réalise, le nombre d’itération n’est pas

connu à priori l’utilisation de schéma for n’est pas adopté
 Remède : utiliser while pour respecter que le nombre
d’itération n’est pas connu à priori

#include<stdio.h>
#define n 100
char * nom[n] ;
int tel [n] ;
int recherche_seq (char * info) /*rend (-1) si info n’appartient pas à
nom sinon elle retourne le
téléphone correspondant*/
{unsigned i ; /*pour parcourir*/
i=0 ;
while( (i<n)&&(strcmp (nom[i] ,info) !=0))
i++;
if (i<n)
return tel[i] ;
return -1 ; }
Remarque :
 Pour l’expression qui gouverne while l’ordre des opérandes
est significatif ceci permet une évaluation connue.
 Dans l’hypothèse où info n’appartient pas au tableau nom,
on soit avec (i>=n) et on n’évalue pas la 2eme opérande
(strcmp(nom[i],info) !=0)
Critique :
 Le schéma while comporte une expression composé (avec
évaluation courte, l’ordre est significatif) on cherche à
simplifier un tel schéma.
Pour y parvenir, on fait appel à la technique de sentinelle.

Exemple
asma abbasi aissao ons benam ben ali
122 125 12 23 2 78 -1
• while (i<n && strcmp(nom[i], info)!=0)

• while( strcmp(nom[i],info)!=0)

Exemple
0 1 2 3 4
Ali Aliou Baba Laila Zina
char* info=’Zina’ ;
La taille initiale est 4 on prévoit un élément de plus (4+1=5),
on commence par mettre la valeur de info dans nom [4] et
puis on engage un recherche séquentielle dans le tableau.
L’expression actuelle :
((i<n)&&strcmp(info,nom[i]) !=0)
Le premier opérande (i<n) on peut l’écarter on obtient alors
strcmp (info,nom[i]) !=0
#include<stdio.h>
#define n 100
Char* nom[n] ;
int tel [n] ;
int recherche_seq (char * info) /*rend (-1) si info n’appartient pas à nom
sinon elle retourne le téléphone correspondant*/
{unsigned i ; /*pour parcourir*/
char* nom[n-1]=(char*) malloc(strlen(info)*sizeof(char)+1);
strcpy(nom[n-1], info) ;
tel [n-1]=-1 ;
i=0 ;
while(strcmp (nom[i], info) !=0)
i++ ;
return tel[i] ;
}

Remarque :
 Dans une structure linéaire (ici tableau) on peut mettre une
sentinelle soit à gauche soit à droite. On ne peut pas aller
haut delà d’une sentinelle.
Recommandation :
 La solution 1 n’est pas recommandée, les solutions 2 et 3
 ok
Complexité :
 Cas minimum: Une seule comparaison : info coïncide avec
le 1er élément
 Cas maximal : n comparaison info coïncide avec le dernier
élément (soit sentinelle ou non )
 cas moyen: n/2 comparaison

• nom [n-1] =
(char*)malloc(strlen(info)*sizeof(char)+1)
• Strcopy(nom[n-1],info);
while(i<n)&&(strcmp(nom[i],info)!=0)

Testing
 Tester un algorithme réalisé dans un langage de
programmation.
 Un test signifie : on connait le jeu de donnée, mettre un
sous-programme qui réalise l’algorithme.
 Egalement, on connait les résultats attendus sur le jeu de
donnée soumis.
 On compare les résultats attendues par rapport au celui
fourni par le sous-programme. En cas de coïncidence, on
dit sue l’algorithme est correct par rapport à ce test sinon il
est incorrect !
 Les tests confirment la présence des erreurs, mais jamais
que le sous-programme est exacte !

Test pour l’algorithme de recherche séquentielle
Echec : info n’appartient pas au nom [ ]
Séquentiel : résultat attendue -1

Résultat fourni -1 ok
sinon un problème
Succès : info appartient au nom [ ] cas limite  info=nom [0]
 info=nom[n-1]
Quelque part au milieu

Algorithme de recherche
dichotomique
Représentation informelle :
 On suppose que le tableau stockant des éléments est trié
par ordre croissant.
 Au lieu d’appliquer l’algorithme de recherche séquentielle
pour voir est ce qu’un élément donnée appartient au
tableau. On possède comme suit :
 On compare l’élément donnée par rapport à l’élément au
milieu du tableau, en cas de coïncidence, on conclut que
l’élément appartient au tableau sinon on recommence la
recherche soit dans la moitié à gauche (si l’élément < à
l’élément au milieu) soit à droite (si l’élément > à
l’élément au milieu) Ceci est répété jusqu’à c que
l’intervalle soit vide.
 intervalle Moitié gauche
Moitié droite
30
15 18 20 30 32 33 56 80 100 112
0 3 9
10
Element au milieu (9+0)/2 =4 Element au milieu (3+2)/2 =2

NON NON
si l’info qu’on cherche est < à si l’info qu’on cherche est < à
val au mileu 32 alors on val au mileu 18 alors on
charche dans la partie gauche charche dans la partie gauche
sinon on cherche dans la sinon on cherche dans la
partie droite partie droite

Réalisation en C : On va appliquer cet algorithme sur l’annuaire
téléphonique
int recherche_dic (char * info) /*rend (-1) si info n’appartient pas à tel sinon elle
retourne le numéro correspondant*/
{int g,d ; /*sous tableau de recherche*/

int m ; /*indice de l’élément au milieu*/
int cmp ; /*résultat entre info et nom [m]*/
/*initialisation*/
g=0 ;
d=n-1 ;
do {m=(g+d)/2 ;
cmp=strcmp(info,nom[m]) ;
if (cmp==0) return tel[m] ;
if (cmp<0) { d=m-1 ;
else g=m+1 ;}
while (g<=d ); } return -1 ; }
• Au min : 1 seule comparaison
• Cas max : Cn le nombre de comparaison
pour N element :
• Cn = CN/2+ 1

Algorithme de recherche
dichotomique
Complexité en Temps
 On va comptabiliser le nombre de comparaison
(strcmp(info,nom[m])?
 Cas minimum : une seule comparaison, un tel cas traduit que
info coinside avec nom [(0+(n-1))/2]
 Cas maximum
Soit CN le nombre de comparaison strcmp(info,nom[m]) d’un tableau
de taille N
CN = CN/2 +1
On pose N=2n => n=log2N
C2n = C2n-1 +1 = C2n-2 +1+1
= C2n-3 +1+1+1
…… = C n-n +n
2
 n=log2N et C1=0
 Cas moyen : la complexité est entre 1 et log2N

Cours Asd Prepa1

Transféré par

Droits d'auteur :

Formats disponibles

Cours Asd Prepa1

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours Asd Prepa1

Transféré par

Droits d'auteur :

Formats disponibles

Algorithme de recherche séquentielle

L’algorithme de recherche séquentielle modélise un problème

GRAIET & HAMEL 2020 124

 Inconvénient : On réalise, le nombre d’itération n’est pas

GRAIET & HAMEL 2020 127

Pour y parvenir, on fait appel à la technique de sentinelle.

GRAIET & HAMEL 2020 129

asma abbasi aissao ons benam ben ali

• while (i<n && strcmp(nom[i], info)!=0)

GRAIET & HAMEL 2020 130

GRAIET & HAMEL 2020 132

GRAIET & HAMEL 2020 133

GRAIET & HAMEL 2020 134

GRAIET & HAMEL 2020 135

Séquentiel : résultat attendue -1

GRAIET & HAMEL 2020 136

Element au milieu (9+0)/2 =4 Element au milieu (3+2)/2 =2

GRAIET & HAMEL 2020 138

{int g,d ; /*sous tableau de recherche*/

int cmp ; /*résultat entre info et nom [m]*/

GRAIET & HAMEL 2020 140

Vous aimerez peut-être aussi

{int g,d ; /sous tableau de recherche/

int cmp ; /résultat entre info et nom [m]/