Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Les algorithmes de recherche
I- La recherche séquentielle
Principe
La méthode de recherche séquentielle d’un élément dans un tableau consiste à parcourir le tableau
élément par élément en les comparant avec l’élément à chercher jusqu’à trouver ce dernier ou
achever le tableau.
Activité : Ecrire un programme qui permet de saisir un tableau T de n entiers avec 2 <= N < 15,
puis vérifier si un entier donné X existe dans le tableau ou non ,en utilisant la méthode de recherche
séquentielle.
Analyse du programme principal • Algorithme du programme principal
Nom Recherche_sequentielle
................................................................................ 0) Debut Recherche_sequentielle
................................................................................ 1) Proc saisie( n )
................................................................................ 2) Proc Remplir( t, n )
................................................................................ 3) Ecrire (‘’Donner la valeur de x’’) lire( x )
................................................................................ 4) Trouve ←FN Recherche_s(x,n,t)
................................................................................ 5) Proc affichage (x,trouve)
.............................................................................. 6) Fin Recherche_sequentielle
FinRecherche_sequentielle
• Tableau de déclaration de nouveau type : • Tableau de déclaration des objets globaux
type Objets Types/Nature Rôle
T Tab Tableau des entiers
Tab = tableau de 14 entiers
N entier Taille du tableau
saisie procédure Procédure de saisie de N
remplir procédure Procédure de remplissage du tableau T.
Recherche Fonction Fonction Booléenne
procédure Procédure d’affichage d’existence ou non
affichage
Algorithme de la fonction Recherche_S de X dans T.
0) DEF FN recherche_s (…,…… :entier ; … :tab) : ……………………
1) ..... ........ , ............... ........
répéter T.D.O Locaux
….. …………… Objet Type Rôle
jusqu'à (…………. ) ou (…………… ) ……… ………….. compteur
………… ……………. Indique l’existence de l’élément
2) Si (……… = x) alors
recherché dans le tableau
…………. vrai
sinon
…………. ………..
FinSi
recherche_s exist
Fin recherche_s
Prof : Mme Houda Boussaid Haddad Page 1
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
program recherchesequentielle;
uses crt; {***** programme Principal*****}
Begin
type Tab=array[1..14]of integer;
var n, x : integer; Trouve :boolean; Saisir(n);
T:tab; Remplir( t, n );
Write ('Donner la valeur de x '); Readln( x );
Trouve := Recherche_s(x,n,t);
Procedure saisir(var n:integer); affichage (x,trouve);
Begin
Repeat End.
write('Donner la taille du tableau : ');
readln(n);
until (n>=2 )and (n<15);
end;
Procedure Remplir(var T:tab;n:integer);
Var i: integer;
Begin
for i:=1 to n do
Begin
write('Donner t[',i,']');
Readln(t[i]);
End;
End;
function Recherche_s (x,n:integer;t:tab):boolean;
var i: integer; exist: boolean;
Begin
i:=0; exist:=false;
Repeat
i:=i+1;
until (t[i] = x) or (i = n);
If t[i] = x then
exist:=true;
Recherche_s:= exist;
End;
Procedure affichage(x:integer; trouve:boolean);
begin
if trouve then
writeln(x,' existe dans le tableau T')
Else
writeln(x,' n''existe pas dans le tableau T');
End;
Prof : Mme Houda Boussaid Haddad Page 2
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Recherche du première position de x dans T
function Recherche_s(x,n:integer;t:tab):integer;
var i:integer; P:integer;
begin
i:=0;
Repeat
i:=i+1;
until (t[i]=x)or (i = n);
If t[i]=x then
Recherche_s:=i;
Recherche_s:= p;
End;
Recherche du dernière position de x dans T
function Recherche_s(x,n:integer;t:tab):integer; Procedure Recherche_s(x,n: integer; t:tab;
Var i:integer; p:integer;
begin var p:integer ) ;
Var i:integer; p:integer;
i:=n+1; begin
Repeat
i:=i-1; i:=n+1;
until (t[i]=x) or (i = 1); Repeat
i:= i-1;
If t[i]=x then
p:=i;
until (t[i]= x) or (i = 1);
Recherche_s:= p;
End; If t[i]=x then
p:=i;
Recherche_s:= p;
End;
Recherche du première et deuxième position
procedure Recherche_s(x,n:integer;t:tab;var p1,p2:integer);
var i,j:integer;
begin
i:=0;
Repeat
i:=i+1;
until (t[i]=x)or (i = n);
If t[i]=x then
p1:=i;
j:=i;
Repeat
j:=j+1;
until (t[j]=x)or (j = n);
If t[j]=x then
p2:=j;
End;
Prof : Mme Houda Boussaid Haddad Page 3
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Recherche du première position de x dans T
program recherchesequentielle;
uses crt;
type Tab = array [1..14] of integer;
var n,x : integer;
T:tab; p:integer;
Function Saisir( ) : integer;
Procedure saisir(var n: integer); Begin
Begin Repeat
Repeat write('Donner la taille du tableau : ');
write('Donner la taille du tableau : '); readln(n);
readln(n); Until (n>=2 )and (n<15);
Until (n>=2 )and (n<15)
end; Saisir:= n ;
End;
Procedure Remplir(var T:tab;n:integer); {***** programme Principal*****}
Var i:integer; Begin
Begin
for i:=1 to n do Saisir(n); N := Saisir ( ) ;
Begin Remplir( t, n );
write('Donner t[',i,']: '); Writeln ('Donner la valeur de x'); Readln( x );
Readln(t[i]); p := Recherche_s(x,n,t);
End; affichage (x,p);
End;
End.
function Recherche_s(x,n:integer;t:tab):integer;
Var i, p:integer ;
begin
i:= 0;
Repeat
i:=i+1;
until (t[i] = x)or (i = n);
If t[i] = x then
p:=i;
Recherche_s:= p;
End;
Procedure affichage(x:integer; p:integer);
begin
if p>0 then
writeln(x,' existe dans le tableau T à la position ',p)
Else
writeln(x,' n''existe pas dans le tableau T');
End;
Prof : Mme Houda Boussaid Haddad Page 4
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Recherche du première et deuxième position de x dansT
program recherchesequentielle;
uses crt;
type Tab=array[1..14]of integer; Procedure affichage(x:integer; p1,p2:integer);
var n,x:integer;
T:tab; p1,p2:integer; begin
if p1>0 then
Procedure saisir(var n:integer); Begin
Begin writeln('la première position de ',x,' est: ',p1);
Repeat if p2>0 then
write('Donner la taille du tableau : '); writeln('la deuxième position de ',x,' est:’,p2)
readln(n); else
until (n>=2 )and (n<15); writeln(x,' n''a pas une deuxième position
end; dans le tableau T ')
end
Procedure Remplir(var T:tab;n:integer); Else
Var i:integer; writeln(x,' n''existe pas dans le tableau T');
Begin
for i:=1 to n do End;
Begin
write('Donner t[',i,']'); {***** programme Principal*****}
Readln(t[i]); Begin
End;
End; Saisir(n);
Remplir( t, n );
procedure Recherche_s(x,n:integer; t:tab; var Writeln ('Donner la valeur de x'); Readln( x );
p1,p2:integer) ; Recherche_s(x,n,t,p1,p2);
var i,j:integer; affichage (x,p1,p2);
begin End.
{** Recherche du première position p1**}
i:=0;
Repeat
i:=i+1;
until (t[i] = x) or ( i = n );
If t[i]=x then
p1:=i;
{** Recherche de deuxième position p2**}
j:= i;
Repeat
j:=j+1;
until (t[j] = x) or ( j = n );
If t[j] = x then
p2:=j;
End;
Prof : Mme Houda Boussaid Haddad Page 5
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Recherche dernière et avant dernière position
program recherchesequentielle;
uses crt; Procedure affichage(x:integer; pf,paf:integer);
type Tab=array[1..14]of integer; begin
var n,x:integer; if pf>0 then
T:tab; pf,paf:integer; Begin
Procedure saisir(var n:integer); writeln(x,' existe dans le tableau T a la
Begin position ',pf);
Repeat if paf>0 then
write('Donner la taille du tableau : '); writeln(' l''avant derniere position de
readln(n); ',x,'dans le tableau T est ',paf)
until (n>=2 )and (n<15); else
end; writeln('l''avant dernière position de ',x,'
n''existe pas');
Procedure Remplir(var T:tab;n:integer); End
Var i:integer; Else
Begin writeln(x,' n''existe pas dans le tableau T');
for i:=1 to n do End;
Begin
write('Donner t[',i,']');
Readln(t[i]); {***** programme Principal*****}
End; Begin
End; Saisir(n);
Remplir( t, n );
Procedure Recherche_s(x,n:integer;t:tab;var Writeln ('Donner la valeur de x'); Readln( x );
pf,paf:integer); Recherche_s(x,n,t,pf,paf);
var i,j:integer; affichage (x,pf,paf);
begin
End.
{** Recherche du dernière position pf**}
i:=n+1;
Repeat
i:=i-1;
until (t[i] = x) or (i = 1);
If t[i] = x then
Pf:=i;
{* Recherche d’avant dernière position
paf*}
J:=i;
Repeat
j:=j-1;
until (t[j]=x)or (j = 1);
If t[j]=x then
paf:=j;
End;
Prof : Mme Houda Boussaid Haddad Page 6
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
II- La Recherche dichotomique
Activité :
Ecrire un programme qui permet de remplir un tableau T de n entiers triés par ordre croissant avec
2<= N < 15,, puis vérifier si un entier donné X existe dans le tableau ou non en utilisant la méthode de
recherche dichotomique.
Principe
1) Déclarer 3 variables
Debut ← Valeur initial du tableau ( = 1 )
Fin← valeur final du tableau( = n)
Milieu ← (debut + fin) Div 2
2) Comparer entre T[milieu] avec la valeur recherché X tel que :
Si ( T[milieu] < X) alors debut ← milieu+1 (il ne reste à traiter que la moitié droite du tableau)
Si ( T[milieu] > X) alors Fin ← milieu-1 (il ne reste à traiter que la moitié gauche du tableau)
Si ( T[milieu] = X) alors l’élément cherché est existant.
3) On répète cette opération jusqu'à ce qu’on trouve l’élément recherché(( T[milieu] = X) ou la
position de début du tableau dépasse la position de fin (debut >Fin)
Solution
Analyse du programme principal • Algorithme du programme principal
Nom Recherche_dichotomique
0) Debut Recherche_dichotomique
1) Proc Remplir( t, n )
Résultat = Proc affichage (x, trouve)
2) Proc saisie_x( x )
Trouve = FN Recherche_dicho(t, n,x)
3) Trouve ←FN Recherche_dicho(t,n,x)
X = Proc saisie_x( x )
4) Proc affichage (x,trouve)
T, n = Proc Remplir(T,n)
5) Fin Recherche_ dichotomique
Fin Recherche_dichotomique
Prof : Mme Houda Boussaid Haddad Page 7
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Algorithme de la fonction Recherche_dicho
0) DEF FN recherche_dicho (…. :tab ; …..,….. :……………..) :…………………….
1) …………….. 1, ………………. n, …………………faux
Répéter
………………. (……………..+……………..) DIV 2
Si (……..=t[…………]) Alors
………………..…………………..
Sinon Si (X<t[……………]) Alors
………………… …………………….
Sinon
Debut …………………………..
FinSi
jusqu'à (…………………) ou (………………..>…………………….)
2) recherche_d ………………..
3) Fin Recherche_dicho
T.D.O Locaux
Objet Type Rôle
………………. …………….. Position de debut pendant la recherche
…………….. …………….. Position de fin pendant la recherche
……………….. ……………… Milieu du tableau
…………….. ………………… Indique l’existence de l’élément recherché dans le tableau
Algorithme de la Procédure Remplir
0) Def Proc Remplir ( Var T :Tab ; var n :integer)
1) Répeter
Ecrire ("Donner la taille du tableau")
Lire(n)
Jusqu'à (n>=2 ) ET ( n < 15)
2) Ecrire("donner T[1] : ")
Lire ( T[1] )
T.D.O Locaux
3) Pour i de 2 à N faire Objet Type Rôle
Répéter i entier compteur
Ecrire("Donner T[ ", i , " ] : ")
Lire ( T[i] )
Jusqu'à ( T[i] > T[i-1] )
Fin Pour
3)Fin Remplir
Prof : Mme Houda Boussaid Haddad Page 8
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Traduction en Pascal
Program Recherche_dichotomique ; begin
Uses wincrt; debut:=1;
Type fin:=n;
tab=array[1..14] of integer; trouve:=false;
Var repeat
T:tab; milieu:= (debut+fin) div 2;
n, x : integer; if X = T[milieu] then
Trouve :boolean ; trouve:=true
{Procedure de lecture de n et de remplissage du else if X < T[milieu] then
tableau T fin :=milieu -1
saisir le premier élément puis saisir les autres else debut:=milieu+1;
éléments du tableau en respectant que les until (trouve) or (debut > fin);
valeurs
du tableau soient triés dans un ordre recherche_dicho:=trouve;
croissant} end;
Procedure Remplir (var T:tab; var n :integer);
Var Procedure affichage(x:integer; trouve:boolean);
i : integer; begin
Begin if trouve then
Repeat writeln(x,' existe dans le tableau T')
Write('Donner la taille du tableau : '); Else
Readln(n) ; writeln(x,' n''existe pas dans le tableau T');
until (n>=2 )and (n<15); End;
Write('Donner T[1] : ');
Readln(T[1]) ;
For i:=2 to n do
begin BEGIN
repeat Remplir (T,n) ;
Write(' Donner T[ ‘ , i ,’ ] : ') ; Saisir_x(X) ;
Readln(T[i]); Trouve := recherche_dicho (T,n,x ) ;
until T[i] > T[i-1] Affichage (x, trouve)
end; End.
end;
{Procedure de saisir l'élément recherché }
Procedure saisir_x(var x:integer);
Begin
write('Donner l’’entier a rechercher : ');
readln(x);
end;
function recherche_dicho
(T:tab;n,x:integer ):boolean;
var
debut,fin,milieu: integer;
trouve: boolean;
Prof : Mme Houda Boussaid Haddad Page 9
Chapitre :Les traitements avancés Lycée Ksibet El Mediouni
Prof : Mme Houda Boussaid Haddad Page 10
