Cours-Informatique.tn| Révision

Révision Informatique

Les méthodes de recherche :

Les méthodes de recherche d'un élément dans un tableau (Recherche séquentielle, Recherche dichotomique).

Introduction :

On va faire la recherche d'un élément dans un tableau. Pour cela on va faire un module permettant, à partir d'un tableau d'entiers T de taille n et de type TAB et d'une valeur V , de renvoyer Vrai si V existe dans T et Faux dans le cas contraire.

Nous sommes dans le cas d'un module renvoyant une seule valeur de type simple (type booléen).

Questions:

You Scored % - /

1. Quel est la nature de ce module :

procédure
fonction

2. Quel est le type de retour de ce module :

booléen
entier

3. Quels sont les paramètres d'entrée de ce module ?

une variable booléenne
le tableau T
la taille du tableau n
la valeur V à chercher

Donc on va utiliser une fonction qui pourra avoir la forme suivante en algorithmique :

0) DEF FN Recherche(T:TAB, n:entier , v:entier)  : booléen
1).....
    .........
..) Recherche ←trouve
..) Fin Recherche

En Pascal:

function recherche(t:TAB;n:integer;v:integer):boolean;
var trouve:boolean;
begin
 { ................}
recherche:=trouve;
end;

On va voir deux méthodes de recherche dans un tableau: séquentielle et dichotomique

1-La recherche séquentielle :

La méthode de recherche séquentielle d'un élément dans un tableau consiste à parcourir le tableau élément par élément progressivement de début vers la fin en les comparant avec l'élément à chercher jusqu'à trouver ce dernier ou achever le tableau.

On ne va pas forcement parcourir le tableau de début vers la fin, puisque dans le cas où on trouve l'élément, on arrête le parcours du tableau et on renvoie Vrai pour dire qu'on a trouvé l'élément à chercher. Par conséquent on va pas utiliser une boucle Pour, pour parcourir le tableau, mais une boucle Répéter .. Jusqu'a

Reprenant le module recherche, renommant le en recherche_sequentielle et essayant de remplir le traitement à faire.

0) DEF FN Recherche_sequentielle(T:TAB, n:entier, v:entier):booléen
1).....
    .........
2) Recherche_sequentielle ←trouve
3) Fin Recherche_sequentielle

Pour faire le parcours avec répéter .. Jusqu'a, on doit utiliser un compteur i qu'il faut l'initialiser avant la boucle (i←0) et assurer son avancement au sein de la boucle (i←i+1) enfin vérifier si on a atteint la fin du tableau (i=n)

0) DEF FN Recherche_sequentielle(T:TAB, n:entier, v:entier):booléen
1) i←0 
    Répéter
    i←i+1
    ......   { Traitement }
    jusqu'a (i=n)
2) Recherche_sequentielle ←trouve
3) Fin Recherche_sequentielle

Question:

L'initialisation du compteur (i←0), son avancement (i←i+1) et le test d'arrêt (i=n) sont liés, par conséquent, si on change l'initialisation (i←1) , quelles sont les modifications à apporter à notre algorithme ?

Voir la réponse..

On va répéter jusqu'a trouver l'élément càd (trouve=vrai) ou achever le tableau (i=n) , et il ne faut pas oublier d'initialiser trouve par faux trouve←faux avant la boucle.

0) DEF FN Recherche_sequentielle(T:TAB, n:entier, v:entier):booléen
1) i←0  , trouve←faux 
    Répéter
    i←i+1
    ......
    jusqu'a (i=n) ou (trouve=vrai)
2) Recherche_sequentielle ←trouve
3) Fin Recherche_sequentielle

Finalement on va ajouter le traitement permettant d'indiquer qu'on a trouvé la valeur v : si T[i]=v alors trouve←vrai Fin Si

Algorithme :

0) DEF FN Recherche_sequentielle(T:TAB, n:entier, v:entier):booléen
1) i←0  , trouve←faux 
    Répéter
    i←i+1
    si T[i]=v alors trouve←vrai  Fin si
    jusqu'a (i=n) ou (trouve=vrai)
2) Recherche_sequentielle ←trouve
3) Fin Recherche_sequentielle

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
i trouve	Entier booléen

Traduction en Pascal:

function recherche_sequentielle(T:tab;n:integer;v:integer):boolean;
var i:integer; trouve:boolean;
begin
    i:=0; trouve:=false;
    repeat
        i:=i+1;
        if t[i]=v then trouve:=true;
    until (trouve) or (i=n);
recherche:=trouve;
end;

Remarque:
-L'expression until (trouve) est équivalente à until (trouve=true)
-On peut faire la recherche séquentielle en utilisant une autre méthode :

Algorithme2 (autre méthode):

0) DEF FN recherche2 (T:TAB,n: entier,v:entier): Booléen
1) i← 0
    Répéter
    i← i+1
    jusqu'a (T[i]=v) ou (i=n)
2) si T[i]=v alors recherche2← VRAI
   sinon recherche2←FAUX
   Fin si
3) Fin recherche2

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
i	Entier

2-La recherche dichotomique :

La méthode de recherche dichotomique consiste à chercher un élément dans un tableau trié.
On compare l'élément à chercher à l'élément central du tableau, s’ils sont différents, un test permet de trouver dans quelle moitié du tableau on peut trouver l'élément.
On contenue ce processus jusqu'à trouver l'élément ou bien arrive à un sous-tableau de taille 1.

Algorithme:

0) DEF FN recherche_dicho (T:TAB,n: entier,v:entier): Booléen
1) a← 1, b← n, trouve← FAUX
    répéter
    m← (a+b) DIV 2
    si T[m]=v alors trouve← VRAI
    sinon si T[m]< v alors a← m+1
                    sinon  b← m-1
    finsi
    jusqu'a (trouve) ou (a>b)
2) recherche_dicho←trouve
3) Fin recherche_dicho

T.D.O locaux(Tableau de déclaration des objets locaux)

Objet	Type/Nature	Rôle
a,b,m trouve	Entier booléen

Traduction en Pascal:

function recherche_dicho(T:tab;n:integer;v:integer):boolean;
var a,b,m:integer;trouve:boolean;
begin
a:= 1 ; b:= n; trouve:=false;
    repeat
        m:=(a+b) div 2;
        si T[m]=v then trouve:=true else
        if T[m]< v then a:=m+1 else  b:=m-1; 
    until (trouve)or (a>b);
recherche_dicho:=trouve;
end;