Les methodes de recherche .pdf


Aperçu du fichier PDF les-methodes-de-recherche.pdf - page 3/5

Page 1 2 3 4 5



Aperçu du document


Niveau Scolaire : 4ème Sciences Expérimentales

préparé par Khaoula ABAIDI

procedure affichageTableau(var t : tab ; n : integer);
var i : integer ;
begin for i:= 1 to n do write(t[i],' '); writeln('');
end;
function rechercheSequentielle(x,n:integer ; t : tab) : boolean ;
var i : integer ; b : boolean;
begin
i := 0 ;
repeat
i := i + 1 ;
until ( t[i] = x ) or (i = n) ;
if t[i] = x then b := true
else b := false ;
rechercheSequentielle := b ;
end;
begin
saisieTaille(taille); remplissageTableau(tr,taille); affichageTableau(tr,taille);
write('Element a chercher '); readln (p);
res := rechercheSequentielle(p,taille,tr) ;
write('Est-ce que l''element ',p,' est existant dans le tableau Tr? ', res);
end.
2) Recherche dichotomique
La recherche dichotomique est une manière efficace et rapide de rechercher un élément dans une
structure de données triée.
Le principe de la recherche dichotomique est le suivant :
a) Trouver la position la plus centrale du tableau (si le tableau est vide, sortir).
b) Comparer la valeur de cette case à l'élément recherché.
c) Si la valeur est égale à l'élément, alors retourner la position, sinon reprendre la procédure dans la
moitié de tableau pertinente.
On peut toujours se ramener à une moitié de tableau sur un tableau trié en ordre croissant. Si la valeur de la
case est plus petite que l'élément, on continuera sur la moitié droite, c'est-à-dire sur la partie du tableau qui
contient des nombres plus grands que la valeur de la case. Sinon, on continuera sur la moitié gauche.
Analyse du module de recherche dichotomique ( Recherche d'un entier dans un tableau Trié)
DEF FN rechercheDichotomique(x : entier ; T : Tab) : booleen
rechercheDichotomique = b
b = [ debut ← 1 , fin ← n , b ← faux ]
Répéter
moitier ← (debut + fin) div 2
si (x = T[moitier]) alors b ← vrai
sinon
si x < T[moitier] alors
fin ← moitier - 1
sinon debut ← moitier + 1
finSi
Jusqu'à (b) ou (debut > fin)
Fin rechercheDichotomique

Les méthodes de recherche

T.D.O
Objet

Type/Nature

debut

Var/entier

fin

Var/entier

moitier

Var/entier

b

Var/booléen

3


Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00584907.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.